LeetCode-15-3Sum

LeetCode-15-3Sum

题目描述：

链接：https://leetcode-cn.com/problems/3sum/

思路分析：

这是一道双指针的变形题。正常的双指针是，nums数组，找两个数，相加和为target，这就很简单了，先给数组排序，然后nums[l] + nums[l] == target的时候，就添加nums[l] + nums[l]到结果中。所以，对题稍作变形，步骤如下：

1. 排序数组。
2. 对数组进行遍历，同时对数组第i到nums.length-1进行双指针找target为nums[i]的情况，就退化为了一个双指针问题。

代码：

class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        for(int i = 0; i < nums.length; i++) {
            helper(nums,i+1,nums.length - 1, nums[i]);
        }
        return ans;
    }
    private void helper(int[] nums, int l, int r, int target) {
        // target 为目标， nums[l] + nums[r] + target == 0 就满足条件 l 和 r为变的
        // 就是 从数组中找两个值，和为-target
        if(l > r) return;
        while(l < r && r < nums.length) {
            int sum = nums[l] + nums[r];
            if(sum + target == 0) {
                // System.out.println(nums[l] + " " + nums[r] + " " + target);
                ans.add(Arrays.asList(nums[l], nums[r], target));
                // 这里也要进行指针移动
                // 因为如果nums[l]==nums[l+1]并且满足和为零的情况，则此时就会出现重复
                // 比如 -2,0,0,2,2
                // target = -2, nums[l] = 0, nums[r] = 2 满足情况 (l=1)
                // target = -2, nums[l] = 0, nums[r] = 2 也满足情况(注意，这里l=2)
                // 所以这么做可以去重
                while(l < r && nums[l] == nums[l+1]) l++;
                while(l < r && nums[r] == nums[r-1]) r--;
                r--;
                l++;
            }
            else if(sum + target > 0) {
                // sum大了，l--
                r--;
            }
            else {
                l++;
            }
        }
    }    
}

调试记录

还有重复项。在对数组进行遍历的时候，也进行去重。

if(i>0 && nums[i]==nums[i-1]) continue; // 去重

class Solution {
    List<List<Integer>> ans = new LinkedList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        for(int i = 0; i < nums.length; i++) {
            if(i>0 && nums[i]==nums[i-1]) continue; // 去重
            helper(nums,i+1,nums.length - 1, nums[i]);
        }
        return ans;
    }
    private void helper(int[] nums, int l, int r, int target) {
        // target 为目标， nums[l] + nums[r] + target == 0 就满足条件 l 和 r为变的
        // 就是 从数组中找两个值，和为-target
        if(l > r) return;
        while(l < r && r < nums.length) {
            int sum = nums[l] + nums[r];
            if(sum + target == 0) {
                // System.out.println(nums[l] + " " + nums[r] + " " + target);
                ans.add(Arrays.asList(nums[l], nums[r], target));
                // 这里也要进行指针移动
                // 因为如果nums[l]==nums[l+1]并且满足和为零的情况，则此时就会出现重复
                // 比如 -2,0,0,2,2
                // target = -2, nums[l] = 0, nums[r] = 2 满足情况 (l=1)
                // target = -2, nums[l] = 0, nums[r] = 2 也满足情况(注意，这里l=2)
                // 所以这么做可以去重
                while(l < r && nums[l] == nums[l+1]) l++;
                while(l < r && nums[r] == nums[r-1]) r--;
                r--;
                l++;
            }
            else if(sum + target > 0) {
                // sum大了，l--
                r--;
            }
            else {
                l++;
            }
        }
    }    
}

AC记录：

总结：

一道非常好的双指针问题，关键点在于如何去重。

// 方法1
if(i>0 && nums[i]==nums[i-1]) continue; // 去重
// 方法2
while(l < r && nums[l] == nums[l+1]) l++;
while(l < r && nums[r] == nums[r-1]) r--;

赏

谢谢你请我吃糖果