Algorithm Four Sum
Description
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]
]
Submission
package com.cctoken.algorithm;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* @author chenchao
*/
public class FourSum {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> finalRes = new LinkedList<List<Integer>>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int target1 = target - nums[i];
for (int j = i + 1; j < nums.length - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int target2 = target1 - nums[j];
int k = j + 1;
int m = nums.length - 1;
while (k < m) {
if (nums[k] + nums[m] < target2) {
k++;
while (k < m && nums[k] == nums[k - 1]) {
k++;
}
} else if (nums[k] + nums[m] > target2) {
m--;
while (k < m && nums[m] == nums[m + 1]) {
m--;
}
} else {
List<Integer> res = new LinkedList<Integer>();
res.add(nums[i]);
res.add(nums[j]);
res.add(nums[k]);
res.add(nums[m]);
finalRes.add(res);
k++;
while (k < m && nums[k] == nums[k - 1]) {
k++;
}
m--;
while(k < m && nums[m] == nums[m + 1]) {
m--;
}
}
}
}
}
return finalRes;
}
public static void main(String[] args) {
// int[] nums = new int[]{1, 0, -1, 0, -2, 2};
int[] nums = new int[]{0, 0, 0, 0};
int target = 1;
new FourSum().fourSum(nums, target);
}
}
Solution
解题思路,参考之前的3个数求和
![](https://img.haomeiwen.com/i6868357/1c6e0560829fa7cf.png)
网友评论