leetcode/Problems/0018.cpp at master · DimitrijeDobrota/leetcode · GitHub

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
30
31
32
33
class Solution {
  public:
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();

        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long long goal = (long long)target - nums[i] - nums[j];
                int k = j + 1, l = n - 1;
                while (k < l) {
                    long long crnt = nums[k] + nums[l];
                    if (crnt > goal)
                        l--;
                    else if (crnt < goal)
                        k++;
                    else {
                        res.push_back({nums[i], nums[j], nums[k], nums[l]});
                        k++, l--;
                        while (k < l && nums[l] == nums[l + 1])
                            l--;
                    }
                }
                while (j + 1 < n && nums[j] == nums[j + 1])
                    ++j;
            }
            while (i + 1 < n && nums[i] == nums[i + 1])
                ++i;
        }
        return res;
    }
};