4Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<vector<int>> fourSum(vector<int> &nums, int target) {
4
    int n = nums.size();
5

6
    vector<vector<int>> answer;
7

8
    if (n < 4) return answer;
9

10
    sort(nums.begin(), nums.end());
11

12
    for (int i = 0; i < n;) {
13
      for (int j = i + 1; j < n;) {
14
        int left = j + 1;
15
        int right = n - 1;
16

17
        long long int x = (long long int)target - (long long int)nums[i] - (long long int)nums[j];
18

19
        while (left < right) {
20
          if (x == nums[left] + nums[right]) {
21
            vector<int> vect{nums[i], nums[j], nums[left], nums[right]};
22
            answer.push_back(vect);
23

24
            // skipping duplicates while moving right
25
            int k = 1;
26
            while ((left + k) < n && nums[left + k] == nums[left]) ++k;
27

28
            if ((left + k) >= n)
29
              break;
30
            else
31
              left = left + k;
32

33
            // skipping duplicates while moving left
34
            k = 1;
35
            while ((right - k) >= 0 && nums[right - k] == nums[right]) ++k;
36

37
            if ((right - k) < 0)
38
              break;
39
            else
40
              right = right - k;
41

42
          } else {
43
            if (x > nums[left] + nums[right]) {
44
              // skipping duplicates while moving right
45
              int k = 1;
46
              while ((left + k) < n && nums[left + k] == nums[left]) ++k;
47

48
              if ((left + k) >= n)
49
                break;
50
              else
51
                left = left + k;
52

53
            } else {
54
              // skipping duplicates while moving left
55
              int k = 1;
56
              while ((right - k) >= 0 && nums[right - k] == nums[right]) ++k;
57

58
              if ((right - k) < 0)
59
                break;
60
              else
61
                right = right - k;
62
            }
63
          }
64
        }
65

66
        // skipping duplicates while moving right
67
        int k = 1;
68
        while ((j + k) < n && nums[j + k] == nums[j]) ++k;
69

70
        if ((j + k) >= n)
71
          break;
72
        else
73
          j = j + k;
74
      }
75

76
      // skipping duplicates while moving right
77
      int k = 1;
78
      while ((i + k) < n && nums[i + k] == nums[i]) ++k;
79

80
      if ((i + k) >= n)
81
        break;
82
      else
83
        i = i + k;
84
    }
85

86
    return answer;
87
  }
88
};