18. 4Sum Medium

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Approach

Input: An integer array nums, a target integer.

Output: Find all unique quadruplets [a, b, c, d] that satisfy a + b + c + d == target.

This is a classic problem of sorting + opposite-direction two pointers.

This problem's solution is similar to 3Sum. We can sort the array first, then fix two numbers nums[a] and nums[b], and then use two pointers in the range b+1 to n-1.

Essentially, after fixing the two numbers nums[a] and nums[b], we refer to finding two other values such that the sum of the four numbers is target.

Implementation

python

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()  # Sort first, helpful for deduplication and two pointers
        n = len(nums)
        res = []

        for a in range(n - 3):
            # Skip duplicate elements
            if a > 0 and nums[a] == nums[a - 1]:
                continue

            # Pruning: The sum of the smallest four numbers is already greater than target, no need to continue
            if nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target:
                break

            # Pruning: The current fixed number plus the sum of the largest three numbers is less than target, skip current
            if nums[a] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
                continue

            for b in range(a + 1, n - 2):
                # Skip duplicate elements
                if b > a + 1 and nums[b] == nums[b - 1]:
                    continue

                # Pruning: The current a, b are fixed, and the sum with the next two smallest numbers is greater than target
                if nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target:
                    break

                # Pruning: The current a, b are fixed, and the sum with the next two largest numbers is less than target
                if nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target:
                    continue

                # Two pointers to find the other two numbers
                left, right = b + 1, n - 1
                while left < right:
                    total = nums[a] + nums[b] + nums[left] + nums[right]
                    
                    if total == target:
                        res.append([nums[a], nums[b], nums[left], nums[right]])
                        left += 1
                        right -= 1

                        # Skip duplicate elements
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1

                    elif total < target:
                        left += 1
                    else:
                        right -= 1

        return res

javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b); // Sort the array first for easier deduplication and two-pointer operations
    const res = [];
    const n = nums.length;

    for (let a = 0; a < n - 3; a++) {
        // Skip duplicates to prevent duplicate results
        if (a > 0 && nums[a] === nums[a - 1]) continue;

        // Pruning: the minimum possible value has already exceeded target, impossible to meet the condition afterwards
        if (nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break;

        // Pruning: the current value plus the largest three numbers is still less than target, skip current
        if (nums[a] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

        for (let b = a + 1; b < n - 2; b++) {
            // Skip duplicates
            if (b > a + 1 && nums[b] === nums[b - 1]) continue;

            // Pruning: the minimum possible value under the current combination exceeds target
            if (nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target) break;

            // Pruning: the maximum possible value under the current combination is still less than target
            if (nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target) continue;

            let left = b + 1;
            let right = n - 1;

            while (left < right) {
                const sum = nums[a] + nums[b] + nums[left] + nums[right];

                if (sum === target) {
                    res.push([nums[a], nums[b], nums[left], nums[right]]);

                    // Skip the duplicate 3rd number
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    left++;

                    // Skip the duplicate 4th number
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    right--;

                } else if (sum < target) {
                    left++; // Total sum is too small, move left pointer to the right
                } else {
                    right--; // Total sum is too large, move right pointer to the left
                }
            }
        }
    }

    return res;
};

Complexity Analysis

• Time Complexity: O(n^3)
• Space Complexity: O(1)

Links

18. 4Sum (English)18. 四数之和 (Chinese)