18. 4 Sum
题目
给出一个具有n个整数的数组S，是否有这样四个元素a，b，c，d，它们满足 a + b + c + d = target？找出所有的四元素组满足目标和。 注意：答案中不能包含重复的四元素组。
代码块
class Solution {
public static List<List<Integer>> fourSum(
int[] nums,
int target) {
List<List<Integer>> result =
new ArrayList<List<Integer>>();
Arrays.sort(nums);
int i =
0 ;
for(i =
0; i < nums.length -
3; i ++){
if(i !=
0 && nums[i] == nums[i -
1]){
continue ;
}
for(
int j = i +
1; j < nums.length -
2; j++){
if(j != i+
1 && nums[j] == nums[j -
1]){
continue ;
}
int start = j +
1;
int end = nums.length -
1;
while ( start < end){
int sum = nums[i] + nums[j] + nums[start] + nums[end];
if(
sum < target){
start ++;
}
else if(
sum > target){
end --;
}
else{
ArrayList<Integer> temp =
new ArrayList<Integer>();
temp.add(nums[i]) ;
temp.add(nums[j]);
temp.add(nums[start]);
temp.add(nums[end]);
start ++;
end --;
result.add(temp);
while(start < end && nums[start]== nums[start -
1]){
start ++;
}
while(start < end && nums[end]== nums[end +
1]){
end --;
}
}
}
}
}
return result;
}
}
代码分析
本题的思想同3Sum，再加一重循环就可以了。 看似简单，我却犯了很多错误。 1. i，j来控制外层循环。判断条件j!=i+1 。不能简单的写成j<1。 2. List《List 《 Integer 》》 result = new ArrayList《List《Integer》》(); Arrays.sort(nums); 这两行总报错，原来没有加包：用“Ctrl+shift +o”来加包。当使用补全功能时自己出来，我可能一开始就没有写对。 注：书名号代替尖括号。 3. 当一切都没问题时，还不能accept，此时，看到exception就恍然大悟：没有去重。然后就补上while（start）以及end 的去重条件，回头看，本代码共有4处去重，四个元素索引都需要进行这个步骤。否则就会出现重复答案。这也是题目中提醒的要求。要注意琢磨每一句话。 错误示例（没有最后两个while）： public static void main(String[] args) { int[] nums = {-1,0,-5,-2,-2,-4,0,1,-2}; System.out.println(fouSum(nums , -9)); } 输出：[[-5, -4, -1, 1], [-5, -4, 0, 0], [-5, -2, -2, 0], [-5, -2, -2, 0], [-4, -2, -2, -1]]
正确的输出应该是： [[-5, -4, -1, 1], [-5, -4, 0, 0], [-5, -2, -2, 0], [-4, -2, -2, -1]]
