# 0018. 4Sums
###### tags: `Leetcode` `双指针`
## 思路
依然是双指针的一道题目，暴力解法的复杂度是$O(N^4)$，因此我们要想一个$O（N^3）$的方法。这道题我的思路是先固定前面两个（用回圈实现），再用双指针找sum和target一样的另外两个数（用l和r实现）。

这道题最大的问题在于答案中不能有重复的，因此就需要满足如下条件：
1.这次选到的i位置的值不能和上一次的重复
2.当固定一个i的时候，这次选到的j位置对应的值不能和上次的重复
3.l和r同理

用code表示如下

还有一点需要注意的是当确定i和j的时候，所能找到的l和r不止有一对，因此当进入到最后的else回圈的时候（代表这四个值可以被写入结果），不能用break跳出回圈，需要让l或r继续移动，(同时也要注意这一次的l对应的值不能和上一次的重复），因此就有了

l++;
while(l<nums.size()-1 && nums[l-1]==nums[l]){l++;}

个人认为这个题目的一个难点是要去限制l和r的范围，防止他找到超出size的地方而产生error，在while回圈那里我原本写的是```while（l！=r）```，结果后来出现问题才发现原来在l和r运算的过程中，l有可能直接跑到r的右边去，所以后来改成```while(l<r)```才正确。由此可以直到双指针的问题，要死死地给他限制住，不然就有可能出问题。

最后，有一个要注意的小点是要看清input的size的限制，这道题有可能给size = 0，1，2，3，所以如果没有在开头加限制，也会出现index超出范围的问题。
## Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        if(nums.size()<4||nums[0]*4>target||nums[nums.size()-1]*4<target){
            return result;
        }
        for(int i = 0; i < nums.size()-3; i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            for(int j = i+1; j < nums.size()-2; j++){
                if(j>i+1 && nums[j]==nums[j-1]){
                  continue;  
                }
                int l = j+1;
                int r = nums.size()-1;
                while(l<r){
                    int sum = nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum > target){
                        r--;
                        while(r>0 && nums[r]==nums[r+1]){
                            r--;
                        }
                    }
                    else if(sum < target){
                        l++;
                        while(l<nums.size()-1 && nums[l-1]==nums[l]){
                            l++;
                        }
                    }
                    else{
                        vector<int> temp = {nums[i],nums[j],nums[l],nums[r]};
                        l++;
                        while(l<nums.size()-1 && nums[l-1]==nums[l]){
                            l++;
                        }
                        result.push_back(temp);
                    }
                }
            }
        }
        return result;
    }
};

## Improvements
经历了无数次失败（Wrong answer和runtime error（index超出范围））之后，第一次的成功在时间上只beat掉了35%的人（哭泣）。直到后来在最开始的if里面加了```nums[0]*4>target||nums[nums.size()-1]*4<target```,才变成beat了86%的人，可见开头就排除的重要性。

## Code in Java

class Solution {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        if (len < 4 || nums[0]*4 > target || nums[len-1]*4 < target) return ans;
        for(int i = 0; i < len - 3; i++){
           if (i > 0 && nums[i] == nums[i-1]) continue;
            for(int j = i + 1; j < len - 2; j++){
                if (j > i+1 && nums[j] == nums[j-1]) continue;
                int l = j + 1;
                int r = len -1;
                while (l < r){
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(sum == target){
                        ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l+1]) l++;
                        while (l < r && nums[r] == nums[r-1]) r--;
                        l++;
                        r--;
                    }else if (sum > target){
                        r--;
                    }else {
                        l++;
                    }
                }
            }
        }
    return ans;
    }
}

## 再优化

// 最开始的时候，如果最小的四个加起来已经比target大了，或者最大的四个之和比target小，那就没必要后边了
if (len < 4 || nums[0]+nums[1]+nums[2]+nums[3] > target || nums[len-1]+nums[len-2]+nums[len-3]+nums[len-4] < target) return ans;


for(int i = 0; i < len - 3; i++){
   if (i > 0 && nums[i] == nums[i-1]) continue;
   \\ 如果最小的四个加起来已经比target大了，那就没必要再loop循环了
   if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
    for(int j = i + 1; j < len - 2; j++){
        if (j > i+1 && nums[j] == nums[j-1]) continue;
        \\ 同理
        if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;