LeetCode15-三数之和

双指针＋排序

public List<List<Integer>> threeSum(int[] nums) {
        //排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        //固定一个值target,范围从头到倒数第三位包含倒数第三位
        for (int k = 0; k < nums.length - 2; k++) {
            //如果固定值大于0,说明整体数组所有元素都大于0,就不可能存在相加等于0的情况
            if (nums[k] > 0) break;
            //如果固定值不是第一位,且当前固定值与前一个固定值相等,就跳过固定值
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            //左指针为固定值的后一个,右指针为数组元素的最后一个
            int l = k + 1, r = nums.length - 1;
            while (l < r) {
                //记录三数之和
                int sum = nums[k] + nums[l] + nums[r];
                //如果三个数小于0,说明左指针太小了,需要调大左指针,使整体的数之和更大一些
                if (sum < 0) {
                    //跳过重复的左指针元素
                    while (l < r && nums[l] == nums[++l]) ;
                    //如果三个数大于0,说明右指针太大了,需要调小右指针,使整体的数之和更小一些
                } else if (sum > 0) {
                    while (l < r && nums[r] == nums[--r]) ;
                } else {
                    //反之就相等加到结果集合里去
                    res.add(new ArrayList<>(Arrays.asList(nums[k], nums[l], nums[r])));
                    //并且继续移动左右的指针并去重
                    while (l < r && nums[l] == nums[++l]) ;
                    while (l < r && nums[r] == nums[--r]) ;
                }
            }
        }
        return res;
    }