Leetcode15

1.问题描述

在这里插入图片描述

2.解决方案

解法一：排序加双指针

a.思路

在这里插入图片描述

b.分析总结

1.关于可行性的检查，相对简单只需要在循环一开始判断就好

//检查可行性
if(nums[i]>0) break;

2.关于越界的解决，首先就是在left和right的移动中呢实际上，会出现越界的情况，那么while条件会帮我们排除一部分，那么如果不continue，会进行下面的 if 条件判断很有可能越界，那么养生好习惯，如果三个 if 只能走一个，每一个 if 结束都加上 continue ，然后就是 left++ 过程中判断 left+1 可能会越界所以在 if 中加入 && 来判断。

//重复性检查
while((left+1)<len&&nums.at(left)==nums.at(left+1)) left++;
left++;
while ((right-1)>=0&&nums.at(right)==nums.at(right-1)) right--;
right--;

//非常关键，就是你变化为可能会有越界，你指望while帮你筛选，那你就赶紧continue防止下面的的if检查中出错
continue;

3.关于重复性的检查

首先呢，在固定的 i 需要有重复检查，这个比较简单如果有重复直接continue

//检查重复性
if(i!=0&&nums.at(i)==nums.at(i-1)) continue;

其次在 left right 移动中也需要重复检查，这是一开始的版本非常的傻，会重复就+2 这种简单思维杜绝，以后一说起重复就至少想成三个重复而不是两个！

//重复性检查
if(nums.at(left)==nums.at(left+1)) left=left+2;
else left++;
if(nums.at(right)==nums.at(right-1)) right=right-2;
else right--;

//非常关键，就是你变化为可能会有越界，你指望while帮你筛选，那你就赶紧continue防止下面的的if检查中出错
continue;

后面改后版本，while并且记住while结束，其实分析可知再加一次才对，其实就是以后一说起重复就至少想成三个重复而不是两个，就对了！

//重复性检查
while((left+1)<len&&nums.at(left)==nums.at(left+1)) left++;
left++;
while ((right-1)>=0&&nums.at(right)==nums.at(right-1)) right--;
right--;

c.代码实现

//排序加双指针
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int len=nums.size();

        //1.必要的检查
        if(len<3) return ans;

        //2.排序
        sort(nums.begin(),nums.end());

        //2.
        for(int i=0;i<len;i++){
            //检查可行性和重复性
            if(nums[i]>0) break;
            if(i!=0&&nums.at(i)==nums.at(i-1)) continue;

            int left=i+1;
            int right=len-1;
            while (left<right){

                if(nums.at(i)+nums.at(left)+nums.at(right)==0){
                    vector<int> v;
                    v.push_back(nums.at(i));
                    v.push_back(nums.at(left));
                    v.push_back(nums.at(right));
                    ans.push_back(v);

                    //重复性检查
                    while((left+1)<len&&nums.at(left)==nums.at(left+1)) left++;
                    left++;
                    while ((right-1)>=0&&nums.at(right)==nums.at(right-1)) right--;
                    right--;

                    //非常关键，就是你变化为可能会有越界，你指望while帮你筛选，那你就赶紧continue防止下面的的if检查中出错
                    continue;
                }
                if(nums.at(i)+nums.at(left)+nums.at(right)>0){
                    while ((right-1)>=0&&nums.at(right)==nums.at(right-1)) right--;
                    right--;

                    continue;
                }
                if(nums.at(i)+nums.at(left)+nums.at(right)<0){
                    while((left+1)<len&&nums.at(left)==nums.at(left+1)) left++;
                    left++;

                    continue;
                }
            }
        }

        //3.
        return ans;
    }
};

解法二：排序加双指针(官方优化)

这个优化说实话，结构很乱，而且我还没看出来为啥效率提高了，在看ing

//官方题解优化
class Solution1 {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};