最后一遍-L18-4Sum
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, and d 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
NOTE:
变换问题，4Sum 转换为 3Sum，3Sum 变为 2Sum的 转换，代码的具体实现的时候，应该怎么处理
重复的问题，是如何解决的
代码的循环的逻辑控制
class Solution {
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res;
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 4) {
res = result;
} else {
Arrays.sort(nums);
long average_value = target / 4;
if (nums[0] > average_value || average_value > nums[nums.length - 1]) {
return result;
}
for (int i = 0; i < nums.length - 3; i++) {
// skip same element
if (i > 0 && nums[i - 1] == nums[i]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
// skip same elements
if (j > i + 1 && nums[j - 1] == nums[j]) continue;
int m = j + 1;
int n = nums.length - 1;
while (m < n) {
// skip same elements
if (m > j + 1 && nums[m - 1] == nums[m]) {
m++;
continue;
}
long tmpSum = (long) nums[i] + (long) nums[j] + (long) nums[m] + (long) nums[n];
if (tmpSum < Integer.MIN_VALUE || tmpSum > Integer.MAX_VALUE) {
break;
}
if (tmpSum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[m], nums[n]));
m++;
n--;
} else if (tmpSum < target) {
m++;
} else {
n--;
}
}
}
}
res = result;
}
return res;
}
}
官方给出来的通解的答案：利用回溯算法和
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, long target, int start, int k) {
List<List<Integer>> res = new ArrayList<>();
// If we have run out of numbers to add, return res.
if (start == nums.length) {
return res;
}
// There are k remaining values to add to the sum. The
// average of these values is at least target / k.
long average_value = target / k;
// We cannot obtain a sum of target if the smallest value
// in nums is greater than target / k or if the largest
// value in nums is smaller than target / k.
if (nums[start] > average_value || average_value > nums[nums.length - 1]) {
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]) {
List<List<Integer>> subsets = kSum(nums, target - nums[i], i + 1, k - 1);
for (List<Integer> subset : subsets) {
List<Integer> tmpSet = new ArrayList<>(Arrays.asList(nums[i]));
tmpSet.addAll(subset);
res.add(tmpSet);
}
}
}
return res;
}
public List<List<Integer>> twoSum(int[] nums, long target, int start) {
List<List<Integer>> res = new ArrayList<>();
int lo = start, hi = nums.length - 1;
while (lo < hi) {
int currSum = nums[lo] + nums[hi];
if (currSum < target || (lo > start && nums[lo] == nums[lo - 1])) {
++lo;
} else if (currSum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1])) {
--hi;
} else {
res.add(Arrays.asList(nums[lo++], nums[hi--]));
}
}
return res;
}
}