public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res =new LinkedList<>();
Arrays.sort(nums);
for(int i = 0 ; i <nums.length-3 ; i++) {
if(i == 0 || (i!= 0 && nums[i] != nums[i-1])) {
for (int j = i+1 ; j<nums.length-2 ; j++) {
if(j == 0 || (j!= 0 && nums[j] != nums[j-1])) {
int lo = j+1 , hi = nums.length-1 , sum = target- nums[i]-nums[j];
while(lo < hi) {
if(nums[lo] + nums[hi] == sum ) {
res.add(Arrays.asList(nums[i] , nums[j] , nums[lo] , nums[hi]));
while(lo<hi && nums[lo] ==nums[lo+1] ) lo++;
while(lo<hi && nums[hi] == nums[hi-1] ) hi--;
lo++;
hi--;
}
else if(sum < nums[lo] + nums[hi])
hi--;
else
lo++;
}
}
}
}
}
return res;
}
}
算法要求:给定数组和target,找出数组中四个数,相加为target。
如输入[1,0,-1,0,-2,2]
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
注:不允许有两个相同的子数组出现在输出中。
代码略微有点复杂,在leetcode下测试是通过的,但是在提交时卡在了输入为[0,0,0,0],target=0上,正确输出应该是[[0,0,0,0]],我的输出为空,我一步步演算,始终是对的,不知道为啥leetcode就是通过不了。