[leetcode] 4sum

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: 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]
]

• 思路和3Sum一样

• Two pointers

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

  public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> lists = new LinkedList<>(); Arrays.sort(nums); int sum; 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 start = j + 1; int end = nums.length - 1; while (start < end) { sum = nums[i] + nums[j] + nums[start] + nums[end]; if (sum == target) { List<Integer> list = new LinkedList<>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[start]); list.add(nums[end]); lists.add(list); start++; end--; while (start < end && nums[start] == nums[start - 1]) { start++; } while (start < end && nums[end] == nums[end + 1]) { end--; } } else if (sum - target > 0) { end--; } else { start++; } } } } return lists; }