Given an integer array nums and an integer target, return every unique group of four values [a, b, c, d] taken from four different positions whose sum equals target. Two groups are the same if they contain the same values, so the answer must not repeat a group. The groups may be returned in any order.
- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every group of four indices costs O(n^4) and still needs a set to remove repeated groups. After sorting, fixing the first two values turns the rest into a sorted Two Sum, which two pointers solve in O(n). That gives O(n^3) overall. Sorting also places equal values next to each other, so skipping a value that equals its left neighbour at each level removes duplicates without any set.
Algorithm
- Sort
nums. - Loop
iover the array, skippingnums[i]if it equalsnums[i-1]. - Loop
jfromi + 1, skippingnums[j]if it equalsnums[j-1](andj > i + 1). - Set
lo = j + 1,hi = n - 1and move them inward: if the sum is too small moveloright, if too big movehileft. - On a match, record the group, then move both pointers past any equal values.
O(n^3)Space: O(1) extra besides the output (sorting aside)int in Java or C++. Do the sum in long. Interviewers often ask for the general k-Sum version: recurse down to the two-pointer case.class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() n = len(nums) res = [] for i in range(n - 3): if i > 0 and nums[i] == nums[i - 1]: continue # same first value as before for j in range(i + 1, n - 2): if j > i + 1 and nums[j] == nums[j - 1]: continue # same second value as before lo, hi = j + 1, n - 1 while lo < hi: s = nums[i] + nums[j] + nums[lo] + nums[hi] if s < target: lo += 1 elif s > target: hi -= 1 else: res.append([nums[i], nums[j], nums[lo], nums[hi]]) lo += 1 hi -= 1 while lo < hi and nums[lo] == nums[lo - 1]: lo += 1 while lo < hi and nums[hi] == nums[hi + 1]: hi -= 1 return res