Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.
Example:
Given array nums = [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]
]
难度：medium
题目：给定一整数数组和一目标整数，是否存在 4 个数的和为指定整数？找出所有这样不同的 4 元组。注意：答案一定不能包含重复的四元组。
思路：数组排序，固定一个数，然后降级为 3sum
Runtime: 34 ms, faster than 78.86% of Java online submissions for 4Sum.Memory Usage: 31.7 MB, less than 13.82% of Java online submissions for 4Sum.
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList();
Arrays.sort(nums);
int numsLen = nums.length;
for (int k = 0; k < numsLen; k++) {
if (0 == k || nums[k – 1] != nums[k]) {
for (int i = k + 1; i < numsLen; i++) {
if ((k + 1) == i || nums[i – 1] != nums[i]) {
for (int left = i + 1, right = numsLen – 1; left < right; left++, right–) {
int sum = nums[left] + nums[right] + nums[i] + nums[k];
if (target == sum
&& ((i + 1) == left || nums[left – 1] != nums[left])
&& ((numsLen – 1) == right || nums[right] != nums[right + 1])
) {
result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
} else if (sum > target) {
left–;
} else {
right++;
}
}
}
}
}
}
return result;
}
}