【CodeTop刷题日记7】三数之和

【CodeTop刷题日记7】三数之和 三数之和

这个题我感觉也是那种不看一次题解就基本不会这么想的题（对于我来说）
虽然是双指针，但是除了这俩 l 和 r 遍历的是另一个值
因此相当于是三指针

一、读题

我一开始还以为是深度搜索，但太菜了没完全写对
看评论区都在说深搜会有仨样例不过
不管了，以后做会了深搜再回头试试这个题吧

二、思路

我能想到先排序，因为这个是返回值，和索引没关系
参考了一个python题解的方式：
就是遍历到的端点右侧是一个区间，我把它叫做 收缩区间

因为是有序的所以以下特性：
（区间左端点l值 + 和区间右端点r值）大于0，就r收一收；小于0，就r缩一缩

注意：剪枝提高效率

1. 重复元素剪枝（去重复是这个题的亮点）
   收缩过程中如果发现下一个和当前相等，直接跳过，避免重复过程
2. 遍历元素大于0剪枝（因为升序，大于0后再加右侧俩值就不可能=0了）

class Solution {
private:
    vector> rs;
    //vector tmp;
public:
    vector> threeSum(vector& nums) {
        if(nums.size() < 3)return rs;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0;i < n;i++){
        	//两个重要剪枝
        	//大于0剪枝
            if(nums[i] > 0) return rs; //不用判断后边的了
            //当有重复元素的时候，只判断第一个
            if(i > 0 && nums[i] == nums[i-1]) continue;
            
            int l = i+1; // 对区间里的内容进行收缩
            int r = n-1;
            while(l < r){
                if(nums[i] + nums[l] + nums[r] == 0){
                    rs.push_back({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(nums[i] + nums[l] + nums[r] < 0){
                    //while(l < r && nums[l] == nums[l+1]) l++;
                    l++;
                }else{
                    //while(l < r && nums[r] == nums[r-1]) r--;
                    r--;
                }
            }
        }
        return rs;
    }
};

Question ？

这里有个小问题不是很懂，就是下面这个步骤按理来说也算剪枝吧
但是加上之后就从击败55.35%变为20%左右了，不太理解

else if(nums[i] + nums[l] + nums[r] < 0){
     //while(l < r && nums[l] == nums[l+1]) l++;
     l++;
}else{
     //while(l < r && nums[r] == nums[r-1]) r--;
     r--;
}

加之前：

加之后：

是因为不加的话总循环也能起到去重效果，而不需要单独写个多余过程来 *** 作么？
欢迎大家评论区批评指正，发表意见～～～谢谢