『LeetCode|每日一题』----＞三数之和

目录

1.每日一句

2.作者简介

『LeetCode|每日一题』三数之和

1.每日一题

2.解题思路

        2.1 思路分析（排序+双指针）

        2.2 核心代码（排序+双指针）

        2.3 完整代码

        2.4 运行结果

---

1.每日一句

你未来的样子藏在你现在的努力里

2.作者简介

🏡个人主页：XiaoXiaoChen-2716 

📚学习专栏：力扣专栏 

🕒发布日期：2022/11/12

『LeetCode|每日一题』三数之和

1.每日一题

原文链接--->点我

2.解题思路

        2.1 思路分析（排序+双指针）

        S1：首先是特殊情况判断，如果数组的元素少于三个，那么就肯定没用解；

        S2：第二步排序，方便我们使用双指针来进行移动计算；

        S3：接下来就开始寻找三个元素，首先对每一组的第一个元素进行判断，由于我们对数组进行了排序，所以如果第一个数都大于0的话那么久肯定没有相加等于0的组合，所以我们直接返回结果；

        S4：根据题目要求，我们还需要进行去重操作，即如果连续两个数是相等的，那么我们应当跳过本次循环进入下次，否则结果会重复；

        S5：接下来就是利用双指针来求和为0的组合，这里我定义了left = i + 1，right = len - 1，当left小于right的时候才进入循环，此时分为三种情况：

1. nums[i] + nums[left] + nums[right] == 0，此时我们需要把这三个元素放到一个链表然后把链表放进结果中，到这还没有结束，接下来同样的是左右两边的去重操作，这里相信读者都能理解，即nums[left] = nums[left + 1]或者nums[right] = nums[right - 1]这两种情况，最后要把指针向中间移动；
2. nums[i] + nums[left] + nums[right] > 0，说明此时右边的数太大了，所以我们把right往左移，即right--；
3. nums[i] + nums[left] + nums[right] < 0，说明左边的数太小了，所以我们把left右移，即left++；

        S6：最后把结果返回即可，因为此题不关心答案的顺序

        2.2 核心代码（排序+双指针）

        Arrays.sort(nums);
        for(int i = 0 ; i < len ; i++){
            if(nums[i] > 0){
                return res;
            }
            if(i >= 1 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while(right > left){
                if(nums[i] + nums[left] + nums[right] == 0){
                    List list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while(left < right && nums[left] == nums[left + 1]){
                    left++;
                    }
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    left += 1;
                    right -= 1;
                }
                else if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else {
                    left++;
                }
            }

        2.3 完整代码

class Solution {
    public List> threeSum(int[] nums) {
        List> res = new ArrayList<>();
        int len = nums.length;
        if(len < 3){
            return res;
        }
        Arrays.sort(nums);
        for(int i = 0 ; i < len ; i++){
            if(nums[i] > 0){
                return res;
            }
            if(i >= 1 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while(right > left){
                if(nums[i] + nums[left] + nums[right] == 0){
                    List list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while(left < right && nums[left] == nums[left + 1]){
                    left++;
                }
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    left += 1;
                    right -= 1;
                }
                else if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else {
                    left++;
                }
            }
        }
        return res;
    }
}

         2.4 运行结果

---

🍁 类似题目推荐：

1.数据结构基础 

2.算法专项练习 

3.剑指offer专项练习

4.推荐一个学习网站：LeetCode，算法的提升在于日积月累，只有每天练习才能保持良好的状态

如果文章对各位大佬有帮助就支持一下噢，不好的地方请各位大佬多多指教！