Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/18.html
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
, andd
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]]
Constraints:
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
Algorithm
Sort the original array, and then start traversing the sorted array. Note that the traversal is not to the last stop, but to the third from the bottom. Here you can do a pruning optimization first, that is, break when traversing to a positive number, because the array is now ordered, if the first number to be fixed is a positive number, then the following numbers If they are all positive numbers, the sum will never be zero.
Then add the process of skipping if repeated. The processing method is to start with the second number. If it is equal to the previous number, skip it because you don’t want to fix the same number twice. For the traversed number, subtract the fix number from 0 to get a target, and then only need to find the sum of the two numbers is equal to the target.
Use two pointers to point to the first and last two numbers of the array starting after the fix number. If the sum of the two numbers happens to be the target, then the two numbers and the fix number are stored in the result together. Then skip the step of repeating numbers. Both pointers need to detect repeated numbers. If the sum of the two numbers is less than the target, move the pointer i
on the left one bit to the right to increase the number pointed to. In the same way, if the sum of the two numbers is greater than the target, move the pointer j
on the right to the left to reduce the number pointed to.
Code
-
// 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; } } }
-
// OJ: https://leetcode.com/problems/4sum/ // Time: O(N^3) // Space: O(1) class Solution { public: vector<vector<int>> fourSum(vector<int>& A, int target) { int N = A.size(); sort(begin(A), end(A)); vector<vector<int>> ans; for (int i = 0; i < N; ++i) { if (i > 0 && A[i] == A[i - 1]) continue; for (int j = i + 1; j < N; ++j) { if (j > i + 1 && A[j] == A[j - 1]) continue; int t = target - A[i] - A[j]; for (int p = j + 1, q = N - 1; p < q; ) { if (A[p] + A[q] == t) { ans.push_back({ A[i], A[j], A[p++], A[q--] }); while (p < q && A[p] == A[p - 1]) ++p; while (p < q && A[q] == A[q + 1]) --q; } else if (A[p] + A[q] < t) ++p; else --q; } } } 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) 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]]) lo += 1 hi -= 1 return res ######### class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: n, res = len(nums), [] if n < 4: return [] nums.sort() for i in range(n - 3): if i > 0 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: if nums[i] + nums[j] + nums[k] + nums[l] == target: res.append([nums[i], nums[j], nums[k], nums[l]]) k += 1 l -= 1 while k < n and nums[k] == nums[k - 1]: k += 1 while l > j and nums[l] == nums[l + 1]: l -= 1 elif nums[i] + nums[j] + nums[k] + nums[l] < target: k += 1 else: l -= 1 return res ############ class Solution(object): def fourSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[List[int]] """ nums.sort() res = [] for i in range(0, len(nums)): if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, len(nums)): if j > i + 1 and nums[j] == nums[j - 1]: continue start = j + 1 end = len(nums) - 1 while start < end: sum = nums[i] + nums[j] + nums[start] + nums[end] if sum < target: start += 1 elif sum > target: end -= 1 else: res.append((nums[i], nums[j], nums[start], nums[end])) start += 1 end -= 1 while start < end and nums[start] == nums[start - 1]: start += 1 while start < end and nums[end] == nums[end + 1]: end -= 1 return res
-
func fourSum(nums []int, target int) [][]int { ans, n := [][]int{}, len(nums) sort.Ints(nums) for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { for l, r := j+1, n-1; l < r; { if nums[i]+nums[j]+nums[l]+nums[r] == target { ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]}) l, r = l+1, r-1 for l < r && nums[l] == nums[l-1] { l++ } for l < r && nums[r] == nums[r+1] { r-- } } else if nums[i]+nums[j]+nums[l]+nums[r] < target { l++ } else { r-- } } for j+1 < n && nums[j+1] == nums[j] { j++ } } for i+1 < n && nums[i+1] == nums[i] { i++ } } return ans }
-
/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function (nums, target) { const n = nums.length; if (n < 4) return []; let res = []; 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 = j + 1; let l = n - 1; while (k < l) { if (nums[i] + nums[j] + nums[k] + nums[l] == target) { res.push([nums[i], nums[j], nums[k], nums[l]]); ++k; --l; while (k < n && nums[k] == nums[k - 1]) ++k; while (l > j && nums[l] == nums[l + 1]) --l; } else if (nums[i] + nums[j] + nums[k] + nums[l] < target) { ++k; } else { --l; } } } } return res; };
-
using System; using System.Collections.Generic; using System.Linq; class FourSumComparer : IEqualityComparer<IList<int>> { public bool Equals(IList<int> left, IList<int> right) { return left[0] == right[0] && left[1] == right[1] && left[2] == right[2] && left[3] == right[3]; } public int GetHashCode(IList<int> obj) { return (obj[0] ^ obj[1] ^ obj[2] ^ obj[3]).GetHashCode(); } } public class Solution { public IList<IList<int>> FourSum(int[] nums, int target) { Array.Sort(nums); var results = new HashSet<IList<int>>(new FourSumComparer()); for (var i = 0; i < nums.Length; ++i) { for (var j = i + 1; j < nums.Length; ++j) { var sum = target - nums[i] - nums[j]; var k = j + 1; var l = nums.Length - 1; var step = (int)Math.Sqrt(nums.Length); while (k < l) { while (k + step < l && nums[k + step] + nums[l] < sum) { k += step; } while (k < l && nums[k] + nums[l] < sum) { k += 1; } if (k < l && nums[k] + nums[l] == sum) { results.Add(new [] { nums[i], nums[j], nums[k], nums[l] }); ++k; } while (k + step < l && nums[k] + nums[l - step] > sum) { l -= step; } while (k < l && nums[k] + nums[l] > sum) { l -= 1; } if (k < l && nums[k] + nums[l] == sum) { results.Add(new [] { nums[i], nums[j], nums[k], nums[l] }); --l; } } } } return results.ToList(); } }
-
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; }