15. 三数之和

题目:https://leetcode-cn.com/problems/3sum/submissions/

代码:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int sum;
        for (int i = 0; i < length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int l = i+1;
            int r = length-1;
            while(l<r){
                sum = nums[i]+nums[l]+nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while (l<r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l<r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else if (sum > 0){
                    r--;
                }
            }
        }
        return res;
    }
}

思路:

1、先将数组按照从小到大进行排序,然后遍历数组。用i做索引

2、对nums[i]进行判断,如果大于0则退出循环。原因:数组是从小到大排列的,如果第一个数都大于0,那么后面的数是大于第一个数的,所以无论如何sum值都不会为0。

3、在遍历nums[i]的时候,设置双指针,一个l一个r,分别从i后面的剩余元素一个左边一个右边进行遍历。在sum值小于0的时候,证明l索引所在的值太小了,需要变大一点即l++;在sum值大于0的时候,证明r索引所在的值太大了,需要变小一点,即r--。

4、经过以上3个条件已经可以得出结果了,但是在某些情况下结果会重复,所以需要进行去重优化,即代码中的第一层for循环中的if语句以及sum=0时的2个while语句。作用都一样。就是判断当前元素是否更上一个元素一样。一样的话得出的结果肯定是重复值,则可以直接跳过。

注意:

1、在去重这里花费的时间比较多。可以好好考虑一下。

2、在找到sum=0的时候,需要将3个元素添加到一个list中,然后再添加到res中,这里可以直接用Arrays.asList()方法做处理。省去自己new一个list然后挨个add的麻烦。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏