leetcode-18. 4Sum

題目描述（中等難度）

給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重複的四元組。

和3Sum類似，只不過是找四個數，使得和為 target，並且不能有重複的序列。如果之前沒有做過3Sum可以先看看，自己在上邊的基礎上加了一個循環而已。

暴力破解法

採用和3Sum解法一相同的暴力破解。

Python

class Solution(object):
    def fourSum(self, nums, target):
        list1=[]
        list2=[]

        for i in range(len(nums)-2):
            for j in range(i+1,len(nums)):
                for k in range(j+1,len(nums)):
                    for l in range(k+1,len(nums)):
                        if(nums[i]+nums[j]+nums[k]+nums[l]==target):
                            list1.append([nums[i],nums[j],nums[k],nums[l]])
        for i in list1:
            a=sorted(i)
            if a not in list2:
                list2.append(a)
        return list2
可以看出已經超出時間限制，由於有四層循環，一般超過三層循環，就會超出時間複雜度。
解法二Java
public class _4sum {
 public static List<List<Integer>> fourSum(int[] num, int target) {
  Arrays.sort(num);
  List<List<Integer>> res=new LinkedList<> ();
  for(int j=0;j<num.length-3;j++) {
   if(j==0 || num[j]!=num[j-1]) {
    for(int i=j+1;i<num.length-2;i++) {
     if(i==j+1 || num[i]!=num[i-1]) {
      int lo=i+1,hi=num.length-1,sum=target-num[j]-num[i];
      while(lo<hi) {
       if(num[lo]+num[hi]==sum) {
        res.add(Arrays.asList(num[j],num[i],num[lo],num[hi]));
        while(lo<hi && num[lo]==num[lo+1]) lo++;
        while(lo<hi && num[hi]==num[hi-1]) hi--;
        lo++;
        hi--;
       }else if(num[lo]+num[hi]<sum) {
        lo++;
       }else {
        hi--;
       }
      }
     }
    }
   }
  }
  return res;
 }
 public static void main(String args[]) {
  int[] num= {1,0,-1,0,-2,2};
  int target=0;
  List<List<Integer>> res=fourSum(num, target);
  System.out.println(res);
 }
}
時間複雜度：O（n³）。
空間複雜度：O（N），最壞情況，即 N 是指 n 個元素的排列組合個數，即