18. 4Sum

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>>  ret;
        int n = nums.size();
        for(int i=0;i<n-3;++i){
            if(i>0 && nums[i] == nums[i-1] )continue;
            for(int j=i+1;j<n-2;++j){
                if(j>i+1 && nums[j] == nums[j-1]) continue;
                int tar = target - nums[i] - nums[j];
                int l = j+1, r = n-1;
                while(l<r){
                    int sum = nums[l] + nums[r];
                    if(sum ==tar){
                        ret.push_back({nums[i], nums[j], nums[l], nums[r]});
                        while(l<r && nums[r] == nums[r-1]) r--;
                        while(l<r && nums[l] == nums[l+1]) l++;
                        l++;
                        r--;
                    }
                    else if(sum <tar) l++;
                    else r--;
                }
            }
        }
        return ret;
    }
};

analysis

  • time complexity O(n^3)
  • space complexity O(1)