leetcode刷题 [java] 15. 三数之和

解题方案

**思路 **

标签：数组遍历

• 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向nums[i]后面的两端，数字分别为 nums[min] 和 nums[max]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集

• 如果 nums[i]大于 0或者nums[max]小于0，则三数之和必然无法等于 0，结束循环

• 如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过

• 当 sum == 0 时，nums[min] == nums[min+1] 则会导致结果重复，应该跳过，min++

• 当 sum == 0 时，nums[max] == nums[max−1] 则会导致结果重复，应该跳过，max—

代码

class Solution {
    public List> threeSum(int[] nums) {
        List> ruList = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0 ;i < nums.length - 1; i++){
            int min = i + 1;
            int max = nums.length - 1;
            if(nums[i]>0 || nums[max]<0) break;
            if(i >0 && nums[i] == nums[i-1]) continue;
            while(min 0 ){
                    while(min < max && nums[max] == nums[—max]);
                }
                else{
                    ruList.add(new ArrayList(Arrays.asList(nums[i], nums[min] , nums[max])));
                    while(min < max && nums[min] == nums[++min]);
                    while(min < max && nums[max] == nums[—max]);
                }
            }
        }
        return ruList;
    }
}

时间复杂度：O(n^2)，n 为数组长度