leetcode-15.三数之和-day15(debug中...)
public List<List<Integer>> threeSum(int[] nums) {
//1.先排序后好用三指针
Arrays.sort(nums);
int k = 0;
//2.特判:第一个数>0,则无;
if (nums[k] > 0) {//注意不能直接返回null
return new ArrayList<List<Integer>>();
}
List<List<Integer>> lists = new ArrayList<>();
//3.当k在倒数第二个位置时,则可以直接return
while (k <= nums.length - 3) {
int i=k+1;
int j = nums.length-1;//while循环注意越界
while (k > 0&&k<nums.length&& nums[k] == nums[k - 1]) {
k++;
}//注意加上下面合适的if判断,不然【0,0,0,0】出问题
if(k>=nums.length-2){
return lists;
}
while (i < j) {
//此处不应该为if,且应该加个i<j,不然【0,0,0】出问题
while(i<j&&(nums[k] + nums[i] + nums[j]) == 0) {
lists.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[k])));
//nums[++i] == nums[i]相当于nums[i+1] == nums[i+1];i++;没赋值,必然的
while (i<j&&nums[i] == nums[++i]) ;
while (j>i&&nums[j] == nums[--j]) ;
}
//(下面两个while需要判断i,j关系)
while (j>i&&(nums[k] + nums[i] + nums[j]) < 0) i++;
while (j>i&&(nums[k] + nums[i] + nums[j]) > 0) j--;
}
k++;
}
return lists;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int k = 0; k < nums.length - 2; k++){
if(nums[k] > 0) break;
if(k > 0 && nums[k] == nums[k - 1]) continue;
int i = k + 1, j = nums.length - 1;
while(i < j){
int sum = nums[k] + nums[i] + nums[j];
if(sum < 0){
while(i < j && nums[i] == nums[++i]);
} else if (sum > 0) {
while(i < j && nums[j] == nums[--j]);
} else {
res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
while(i < j && nums[i] == nums[++i]);
while(i < j && nums[j] == nums[--j]);
}
}
}
return res;
}
}