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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
Solution 1:递归解法超时，忘记了数组已经排好序，最里层2sum的时候直接用两个指针即可
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
List<List<Integer>> res = sub(num, target, 0, 4);
return res == null ? new ArrayList<List<Integer>>() : res;
}
private List<List<Integer>> sub(int[] num, int target, int index, int numbers) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (target == 0 && numbers == 0) {
result.add(new ArrayList<Integer>());
return result;
}
if (numbers < 0 || (index >= num.length || num[index] > target)) {
return null;
}
for (int i = index; i < num.length; i++) {
List<List<Integer>> lists = sub(num, target - num[i], i+1, numbers-1);
if (lists != null && lists.size() > 0) {
for (List<Integer> list : lists) {
list.add(0, num[i]);
result.add(list);
}
}
int tmp = i + 1;
while (tmp < num.length && num[tmp] == num[i]) {
tmp++;
}
i = tmp - 1;
}
return result;
}
}
Solution 2:
注意最里层对于重复数字的处理，只有当num[start] + num[end] == twoSumTarget满足时，才跳过剩下的重复数字，否则e.g. target＝ 4， 对于［2，2，4］，如果先跳过重复数字的话［2，2］会miss
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i = 0; i < num.length; i++) {
for (int j = i + 1; j < num.length; j++) {
int twoSumTarget = target - num[i] - num[j];
int start = j + 1, end = num.length - 1;
while (start < end) {
if (num[start] + num[end] == twoSumTarget) {
List<Integer> list = new ArrayList<Integer>();
list.add(num[i]);
list.add(num[j]);
list.add(num[start]);
list.add(num[end]);
result.add(list);
int tmp = start + 1;
while (tmp < end && num[tmp] == num[start]) {
tmp++;
}
start = tmp;
tmp = end - 1;
while (tmp > start && num[tmp] == num[end]) {
tmp--;
}
end = tmp;
} else if (num[start] + num[end] < twoSumTarget) {
start++;
} else {
end--;
}
}
int tmp = j + 1;
while (tmp < num.length && num[tmp] == num[j]) {
tmp++;
}
j = tmp - 1;
}
int tmp = i + 1;
while (tmp < num.length && num[tmp] == num[i]) {
tmp++;
}
i = tmp - 1;
}
return result;
}
}
Solution 3:另外一种解法是利用3sum
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i = 0 ;i < num.length - 3; i++) {
List<List<Integer>> tmp = threeSum(num, i + 1, target - num[i]);
if (tmp != null && !tmp.isEmpty()) {
for (List<Integer> list : tmp) {
list.add(0, num[i]);
result.add(list);
}
}
while (i + 1 < num.length && num[i+1] == num[i]) {
i++;
}
}
return result;
}
private List<List<Integer>> threeSum(int[] num, int index, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (int i = index; i < num.length - 2; i++) {
int sum = target - num[i];
int start = i+1, end = num.length - 1;
while (start < end) {
if (num[start] + num[end] == sum) {
List<Integer> list = new ArrayList<Integer>();
list.add(num[i]);
list.add(num[start]);
list.add(num[end]);
result.add(list);
while (start + 1 < end && num[start+1] == num[start]) {
start++;
}
while (end - 1 > start && num[end-1] == num[end]) {
end--;
}
start++;
end--;
} else if (num[start] + num[end] < sum) {
while (start + 1 < end && num[start+1] == num[start]) {
start++;
}
start++;
} else {
while (end - 1 > start && num[end-1] == num[end]) {
end--;
}
end--;
}
}
while (i + 1 < num.length && num[i+1] == num[i]) {
i++;
}
}
return result;
}
}
codesolutiony 