leetcode-solutions/0018_4sum.cc at main · deantee/leetcode-solutions · 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>

using namespace std;

class Solution {
 public:
  vector<vector<int>> fourSum(vector<int>& nums, int target) {
    int n(nums.size());
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    for (int i{}; i < n - 3; ++i) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      if ((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] <
          target) {
        continue;
      }
      if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] >
          target) {
        break;
      }
      for (int j{i + 1}; j < n - 2; ++j) {
        if (j > i + 1 && nums[j] == nums[j - 1]) {
          continue;
        }
        if ((long long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
          continue;
        }
        if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
          break;
        }
        int l{j + 1};
        int r{n - 1};
        while (l < r) {
          long long s{(long long)nums[i] + nums[j] + nums[l] + nums[r]};
          if (s == target) {
            ans.push_back({nums[i], nums[j], nums[l], nums[r]});
            do {
              ++l;
            } while (l < r && nums[l] == nums[l - 1]);
            do {
              --r;
            } while (l < r && nums[r] == nums[r + 1]);
          } else if (s < target) {
            ++l;
          } else {
            --r;
          }
        }
      }
    }
    return ans;
  }
};