Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2)
Solution:
Sorting helps us to deal with both constraints. Keep 4 pointers. We move the 1st pointer from left to right, and each time solve a 3SUM problem using the other 3 pointers in the subarray with index ranging from i + 1 to n.
Complexity: O(n^3). Since 3SUM can be solved in O(n^2) time.
Further reading: [LeetCode] 3SUM
Complexity: O(n^3). Since 3SUM can be solved in O(n^2) time.
Further reading: [LeetCode] 3SUM
public class Solution { private ArrayList<Integer> quadruplet( int[] nums, int i, int j, int k, int l ) { ArrayList<Integer> li = new ArrayList<Integer>(); li.add(nums[i]); li.add(nums[j]); li.add(nums[k]); li.add(nums[l]); return li; } public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); ArrayList<List<Integer>> list = new ArrayList<List<Integer>>(); for (int i = 0; i < nums.length - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.length - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } int k = j + 1; int l = nums.length - 1; while (k < l) { int sum = nums[i] + nums[j] + nums[k] + nums[l]; if (sum == target) { list.add(quadruplet(nums, i, j, k, l)); k++; l--; while (k < l && nums[k] == nums[k - 1]) { k++; } while (k < l && nums[l] == nums[l + 1]) { l--; } } else if (sum < target) { k++; } else { l--; } } } } return list; } }
No comments:
Post a Comment