/ Data Structure and Algorithms  

Leetcode 18: 4Sum

Question



Similar to Question 15: 3Sum. This time we want to find all 4 numbers that add up to the target value.

Similar Questions

Soultion

The idea is excatly same with Question 15: 3Sum. Just adding another layer of for loop.

  1. Sort the array
  2. First for loop to get the first number. (0 - num.length - 3)
  3. Use an If statement to avoid duplicate. (Skip the same number)
  4. Second for loop to get second number. (i + 1 to num.length - 2)
  5. Another If statement to avoid duplicate. (Skip the same number)
  6. Now we use 2 pointers head and tail to find remaining 2 numbers
  7. sum = target - num[i] - num[j]
  8. Depending on the comparison of sum and target:
    8.1 sum = target: add to the result list, and move inward head and tail until all same number are skipped
    8.2 sum < target: head++
    8.3 sum > target: tail--
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
List<List<Integer>> results = new ArrayList<>();

Arrays.sort(nums);

// first for loop to get first number
for (int i = 0; i < nums.length; i++) {
    // to avoid duplicate
    if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
        // second for loop to get second number
        for (int j = i + 1; j < nums.length; j++) {
            // to avoid duplicate
            if (j == i + 1 || (j > 0 && nums[j] != nums[j - 1])) {
                int low = j + 1;
                int high = nums.length - 1;

                int sum = target - nums[i] - nums[j];

                // find remaining 2 numbers
                while (low < high) {
                    // find the results
                    if (nums[low] + nums[high] == sum) {
                        results.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));

                        low++;
                        high--;

                        // skip same number
                        while (low < high && nums[low] == nums[low - 1]) {
                            low++;
                        }

                        // skip same number
                        while (low < high && nums[high] == nums[high + 1]) {
                            high--;
                        }
                    } else if (nums[low] + nums[high] > sum) {
                        high--;
                    } else {
                        low++;
                    }
                }
            }
        }
    }
}

return results;

Time complexity O(n3), and space complexity O(1).