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的麻烦。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

Bloombagz大型大号种树袋环保透气双提手控根大花盆阳台庭院户外种植袋生长袋简约灰可种2米树20加仑
¥35.10
科德宝(micronAir)空调滤清器空调滤芯CF095(适用起亚K2(15-20年)/K4/K3 20年后/凯绅/福瑞迪18年后/KX5)
¥43.90
乐活时光 简易衣帽架落地衣架家用室内单杆式晾衣服架子挂衣架落地晒衣杆卧室多功能置物架 黑色110cm宽-双边树杈【店长推荐款!】
¥35.90
雷士照明(NVC)LED日光灯管T8灯管1.2米16W正白光6500K (不含支架 需自购支架)
¥18.60
钢铁是怎样炼成的/全本无删减 无障碍阅读 八年级下必读 (赠京师大讲堂视频解析)
¥22.14
海俪恩(HORIEN)氧眼清眸近视隐形眼镜半年抛2片装小直水润透氧抗UV官网旗舰店带度数透明隐形镜片 2片装 150度
¥35.00
艾薇 儿童枕巾学生成人全棉纱布三层夹棉枕头巾一个装 52*78cm 小鹿蓝
¥15.80
亮湃HARPIC多效合一洁厕液活力海洋750ml 英国进口洁厕灵 马桶清洁剂 强力去污去垢除垢除菌去味
¥26.90