[LeetCode][Java] 4Sum

題目：

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

   

      For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
  
      A solution set is:
      (-1,  0, 0, 1)
      (-2, -1, 1, 2)
      (-2,  0, 0, 2)

  
  

  題意：

  給定一個包含n個整數的數組S,在數組S中是否存在元素a,b,c和d,使得 a + b + c + d = target.找出數組S中所有這樣的組合。

  注意：

  1.這四個元素必須是升序排列(ie, a ≤ b ≤ c ≤ d)

  2.最終結果中不嫩包含重復的解。

   

      For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
  
      A solution set is:
      (-1,  0, 0, 1)
      (-2, -1, 1, 2)
      (-2,  0, 0, 2)

  
  

   

  算法分析：

  * 利用了題目《3Sum》的代碼 https://leetcode.com/problems/3sum/
  * 首先升序排列數組，然後從第一個元素開始依次遍歷《3Sum》算法，目標值為（target-nums[i]）,遍歷的數組為該元素後面的數組
  * 這樣既滿足最終的arraylist中元素升序排列，也不會出現重復，因為每次以其為開始，進行遍歷的元素都是數組中的最小的元素

  AC代碼：

   

  public class Solution 
  {
      private static ArrayList> ret = new ArrayList>();
      
      public ArrayList> fourSum(int[] nums, int target) 
      {
          int newtarget=0;
      
          ArrayList> finalres = new ArrayList>();
          Arrays.sort(nums);
      	for (int i = 0; i < nums.length; i++) 
          {
      		 ArrayList> temlist= new ArrayList>();
      		if (i > 0 && nums[i] == nums[i-1]) continue;//避免結果重復，其後面和它相等的直接被跳過。
              newtarget=target-nums[i];
              int inputnums[]=new int[nums.length -i-1];
              for(int ii=0;ii> threeSum(int[] num,int newtarget,int firstnum) 
      {
          if (num == null || num.length < 3) return ret;
          
          Arrays.sort(num);
          
          int len = num.length;
          for (int i = 0; i < len-2; i++) 
          {
              if (i > 0 && num[i] == num[i-1]) continue;//避免結果重復，其後面和它相等的直接被跳過。
              find(num, i+1, len-1, num[i],newtarget, firstnum); //尋找兩個數與num[i]的和為0
          }
          
          return ret;
      }
      
      public static void find(int[] num, int begin, int end, int target,int newtarget,int firstnum) 
      {
          int l = begin, r = end;
          while (l < r)
          {
              if (num[l] + num[r] + target == newtarget) 
              {
                  ArrayList ans = new ArrayList();
                  ans.add(firstnum);//與原始的《3Sum》算法不同的地方為:記得把每次的啟示遍歷元素加入進去，就是4個數中的最小的那一個
                  ans.add(target);
                  ans.add(num[l]);
                  ans.add(num[r]);
                  ret.add(ans); //放入結果集中
                  while (l < r && num[l] == num[l+1]) l++;//避免結果重復，其後面和它相等的直接被跳過。
                  while (l < r && num[r] == num[r-1]) r--;////避免結果重復，其後面和它相等的直接被跳過。
                  l++;
                  r--;
              } 
              else if (num[l] + num[r] + target < newtarget) 
                  l++;
              else 
                  r--;
          }
      }
  }