# 18. 4Sum

XAMPP相关 746浏览

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

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])
) {
} else if (sum > target) {
left–;
} else {
right++;
}
}
}
}
}
}

return result;
}
}