Welcome to Subscribe On Youtube
18. 4Sum
Description
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 < na,b,c, anddare 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]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
Solutions
Solution 1: Sorting + Double Pointers
We notice that the problem requires us to find non-repeating quadruplets. Therefore, we can first sort the array, which makes it easy to skip duplicate elements.
Next, we enumerate the first two elements of the quadruplet, $nums[i]$ and $nums[j]$, where $i \lt j$. During the enumeration process, we skip duplicate $nums[i]$ and $nums[j]$. Then, we use two pointers $k$ and $l$ to point to the two ends behind $nums[i]$ and $nums[j]$. Let $x = nums[i] + nums[j] + nums[k] + nums[l]$, we compare $x$ with $target$ and perform the following operations:
- If $x \lt target$, then update $k = k + 1$ to get a larger $x$;
- If $x \gt target$, then update $l = l - 1$ to get a smaller $x$;
- Otherwise, it means that a quadruplet $(nums[i], nums[j], nums[k], nums[l])$ is found. Add it to the answer, then we update the pointers $k$ and $l$, and skip all duplicate elements to prevent the answer from containing duplicate quadruplets, and continue to find the next quadruplet.
The time complexity is $O(n^3)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.
-
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { int n = nums.length; List<List<Integer>> ans = new ArrayList<>(); if (n < 4) { return ans; } Arrays.sort(nums); 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 k = j + 1, l = n - 1; while (k < l) { long x = (long) nums[i] + nums[j] + nums[k] + nums[l]; if (x < target) { ++k; } else if (x > target) { --l; } else { ans.add(List.of(nums[i], nums[j], nums[k++], nums[l--])); while (k < l && nums[k] == nums[k - 1]) { ++k; } while (k < l && nums[l] == nums[l + 1]) { --l; } } } } } return ans; } } // // general solution, k-sum // https://leetcode.com/problems/4sum/solution/ // below kSum() divide-and-conquer idea is good, but not passing Online-Judge class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); return kSum(nums, target, 0, 4); } public List<List<Integer>> kSum(int[] nums, int target, int start, int k) { List<List<Integer>> res = new ArrayList<>(); if (start == nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k) return res; if (k == 2) return twoSum(nums, target, start); for (int i = start; i < nums.length; ++i) if (i == start || nums[i - 1] != nums[i]) // 'i == start' is key, since it could be in a following recurion of [1,1,1] where start is 3rd '1' for (List<Integer> set : kSum(nums, target - nums[i], i + 1, k - 1)) { res.add(new ArrayList<>(Arrays.asList(nums[i]))); res.get(res.size() - 1).addAll(set); } return res; } public List<List<Integer>> twoSum(int[] nums, int target, int start) { List<List<Integer>> res = new ArrayList<>(); int lo = start, hi = nums.length - 1; while (lo < hi) { int sum = nums[lo] + nums[hi]; if (sum < target || (lo > start && nums[lo] == nums[lo - 1])) ++lo; else if (sum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1])) --hi; else res.add(Arrays.asList(nums[lo++], nums[hi--])); } return res; } } public class Four_Sum { public static void main(String[] args) { Four_Sum out = new Four_Sum(); Solution s = out.new Solution(); // SolutionForLoop s= out.new SolutionForLoop(); List<List<Integer>> result = s.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0); for (List<Integer> each : result) { String one = ""; for (int e : each) { one = one + " " + e; } System.out.println(one); } } // time: O(NlogN) // space: O(1) public class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); if (nums.length < 4) { return list; } Arrays.sort(nums); // improved based on 3-sum int layer4 = 0; while (layer4 < nums.length) { // @note: below is causing me trouble when convert for to while // in while, here "layer4" is never updated for case like {0,0,0,0} // if(layer4 > 0 && nums[layer4] == nums[layer4 - 1]) continue; if (layer4 > 0 && nums[layer4] == nums[layer4 - 1]) { layer4++; } // hold one pointer, other two pointer moving int ancher = layer4 + 1; while (ancher < nums.length) { int i = ancher + 1; int j = nums.length - 1; while (i < j) { int sum = nums[layer4] + nums[ancher] + nums[i] + nums[j]; if (sum == target) { // @note: Arrays.asList() list.add(Arrays.asList(nums[layer4], nums[ancher], nums[i], nums[j])); // @note: dont forget move pointers i++; j--; // @note: optimization. above i,j is updated already, compare with previous position while (i < j && nums[i] == nums[i - 1]) { i++; } while (j > i && nums[j] == nums[j + 1]) { j--; } } else if (sum < target) { i++; // @note: same here, possibly updated already, note i-1 or i+1 while (i < j && nums[i] == nums[i - 1]) { i++; } } else { j--; // @note: same here, possibly updated already, note i-1 or i+1 while (j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) { j--; } } } ancher++; // optimize for 2nd pointer while (ancher > layer4 && ancher < nums.length && nums[ancher] == nums[ancher - 1]) { ancher++; } } layer4++; // optimize for 2nd pointer while (layer4 < nums.length && nums[layer4] == nums[layer4 - 1]) { layer4++; } } return list; } } } -
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n = nums.size(); vector<vector<int>> ans; if (n < 4) { return ans; } sort(nums.begin(), nums.end()); for (int i = 0; i < n - 3; ++i) { if (i && 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 k = j + 1, l = n - 1; while (k < l) { long long x = (long long) nums[i] + nums[j] + nums[k] + nums[l]; if (x < target) { ++k; } else if (x > target) { --l; } else { ans.push_back({nums[i], nums[j], nums[k++], nums[l--]}); while (k < l && nums[k] == nums[k - 1]) { ++k; } while (k < l && nums[l] == nums[l + 1]) { --l; } } } } } return ans; } }; -
# k-sum class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() return self.kSum(nums, target, 0, 4) def kSum(self, nums: List[int], target: int, start: int, k: int) -> List[List[int]]: res = [] if start == len(nums) or nums[start] * k > target or target > nums[-1] * k: return res if k == 2: return self.twoSum(nums, target, start) for i in range(start, len(nums)): if i == start or nums[i - 1] != nums[i]: # here is a hidden matching target==0 # if not matching target, then kSum() will return empty list for sset in self.kSum(nums, target - nums[i], i + 1, k - 1): # if kSum(k-1) return empty, it will not execute this line res.append([ nums[i] ] + sset) # put nums[i] in a list return res def twoSum(self, nums: List[int], target: int, start: int) -> List[List[int]]: res = [] lo, hi = start, len(nums) - 1 while lo < hi: s = nums[lo] + nums[hi] if s < target or (lo > start and nums[lo] == nums[lo - 1]): lo += 1 elif s > target or (hi < len(nums) - 1 and nums[hi] == nums[hi + 1]): hi -= 1 else: res.append([nums[lo], nums[hi]]) # continue searching, could be multiple answers lo += 1 hi -= 1 return res ######### class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: n = len(nums) ans = [] if n < 4: return ans nums.sort() for i in range(n - 3): if i and nums[i] == nums[i - 1]: continue for j in range(i + 1, n - 2): if j > i + 1 and nums[j] == nums[j - 1]: continue k, l = j + 1, n - 1 while k < l: x = nums[i] + nums[j] + nums[k] + nums[l] if x < target: k += 1 elif x > target: l -= 1 else: ans.append([nums[i], nums[j], nums[k], nums[l]]) k, l = k + 1, l - 1 while k < l and nums[k] == nums[k - 1]: k += 1 while k < l and nums[l] == nums[l + 1]: l -= 1 return ans -
func fourSum(nums []int, target int) (ans [][]int) { n := len(nums) if n < 4 { return } sort.Ints(nums) for i := 0; i < n-3; i++ { if i > 0 && nums[i] == nums[i-1] { continue } for j := i + 1; j < n-2; j++ { if j > i+1 && nums[j] == nums[j-1] { continue } k, l := j+1, n-1 for k < l { x := nums[i] + nums[j] + nums[k] + nums[l] if x < target { k++ } else if x > target { l-- } else { ans = append(ans, []int{nums[i], nums[j], nums[k], nums[l]}) k++ l-- for k < l && nums[k] == nums[k-1] { k++ } for k < l && nums[l] == nums[l+1] { l-- } } } } } return } -
function fourSum(nums: number[], target: number): number[][] { const n = nums.length; const ans: number[][] = []; if (n < 4) { return ans; } nums.sort((a, b) => a - b); for (let i = 0; i < n - 3; ++i) { if (i > 0 && nums[i] === nums[i - 1]) { continue; } for (let j = i + 1; j < n - 2; ++j) { if (j > i + 1 && nums[j] === nums[j - 1]) { continue; } let [k, l] = [j + 1, n - 1]; while (k < l) { const x = nums[i] + nums[j] + nums[k] + nums[l]; if (x < target) { ++k; } else if (x > target) { --l; } else { ans.push([nums[i], nums[j], nums[k++], nums[l--]]); while (k < l && nums[k] === nums[k - 1]) { ++k; } while (k < l && nums[l] === nums[l + 1]) { --l; } } } } } return ans; } -
/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function (nums, target) { const n = nums.length; const ans = []; if (n < 4) { return ans; } nums.sort((a, b) => a - b); for (let i = 0; i < n - 3; ++i) { if (i > 0 && nums[i] === nums[i - 1]) { continue; } for (let j = i + 1; j < n - 2; ++j) { if (j > i + 1 && nums[j] === nums[j - 1]) { continue; } let [k, l] = [j + 1, n - 1]; while (k < l) { const x = nums[i] + nums[j] + nums[k] + nums[l]; if (x < target) { ++k; } else if (x > target) { --l; } else { ans.push([nums[i], nums[j], nums[k++], nums[l--]]); while (k < l && nums[k] === nums[k - 1]) { ++k; } while (k < l && nums[l] === nums[l + 1]) { --l; } } } } } return ans; }; -
public class Solution { public IList<IList<int>> FourSum(int[] nums, int target) { int n = nums.Length; var ans = new List<IList<int>>(); if (n < 4) { return ans; } Array.Sort(nums); 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 k = j + 1, l = n - 1; while (k < l) { long x = (long) nums[i] + nums[j] + nums[k] + nums[l]; if (x < target) { ++k; } else if (x > target) { --l; } else { ans.Add(new List<int> {nums[i], nums[j], nums[k++], nums[l--]}); while (k < l && nums[k] == nums[k - 1]) { ++k; } while (k < l && nums[l] == nums[l + 1]) { --l; } } } } } return ans; } } -
class Solution { /** * @param int[] $nums * @param int $target * @return int[][] */ function fourSum($nums, $target) { $result = []; $n = count($nums); sort($nums); for ($i = 0; $i < $n - 3; $i++) { if ($i > 0 && $nums[$i] === $nums[$i - 1]) { continue; } for ($j = $i + 1; $j < $n - 2; $j++) { if ($j > $i + 1 && $nums[$j] === $nums[$j - 1]) { continue; } $left = $j + 1; $right = $n - 1; while ($left < $right) { $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right]; if ($sum === $target) { $result[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]]; while ($left < $right && $nums[$left] === $nums[$left + 1]) { $left++; } while ($left < $right && $nums[$right] === $nums[$right - 1]) { $right--; } $left++; $right--; } elseif ($sum < $target) { $left++; } else { $right--; } } } } return $result; } }