18. 4Sum

Sort, fix the first two numbers with nested loops, then two-pointer the remaining pair — the same idea as 3Sum with one more outer loop. Skip duplicates at every level.

Extend 3Sum by one level

Sort the array. Fix nums[i] and nums[j] with two nested loops, then run a two-pointer search on the suffix for the remaining target - nums[i] - nums[j]. Skipping equal neighbours at each of the four positions avoids duplicate quadruplets.

sort(nums)
for i: skip dup
  for j>i: skip dup
    lo,hi = j+1, n-1
    while lo<hi: move pointers by comparing the 4-sum to target, skip dups on a hit

Use 64-bit sums to avoid overflow.

Worked example

nums=[1,0,-1,0,-2,2], target=0 → [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]].

Complexity

• Time: O(n³).
• Space: O(1) extra (excluding output).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        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 lo = j + 1, hi = n - 1;
                while (lo < hi) {
                    long s = (long) nums[i] + nums[j] + nums[lo] + nums[hi];
                    if (s == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[lo], nums[hi]));
                        lo++; hi--;
                        while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                        while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                    } else if (s < target) {
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
        }
        return res;
    }
}