『 基础算法题解 』之双指针（下）

三数之和

题目解析

【题目链接】

本题的关键信息:

• a,b,c三数之和为0;

• 不重复的三元组

  以示例1为例,三元组为[-1,0,1],[-1,0,1],[-1,-1,2];

  但最终答案为[[-1,0,1],[-1,-1,2]];

算法原理

• 双指针

  该算法原理可以参考上一题和为S的两个数,具体的思路为将数组首先进行一次排序使其具有单调性;

  再通过和为S的两个数的思路进行;

  具体为:

  1. 固定好一个数据(最左),在该数据的右侧区间内找到和为该数的相反数的两个数;

     

  2. 由于需要找到数组中所有这样的数据,所以在找到一组数据后应该继续找;

  同时在该题中应该要特别注意一个细节:

  • 去重

  该数据中返回的所有三元组和都将是不重复的,具体的去重方法有两种:

  1. 使用unordered_set容器进行去重;

  2. 控制指针,当指针所指数据与上一位置数据相同则会出现三元组重复的可能;

     所以分别控制cur,lefy,right指针即可;

  小优化:由于数据经排序后已经具有单调性,所以当cur所指位置数据>0时,则代表cur后区间的数据中已经不满足三数之和>0,所以cur所指位置数据>0时,可以直接跳出循环;

代码

• 双指针

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> ret;
        sort(nums.begin(),nums.end());//排序使数组具有单调性

        int len = nums.size();
        int cur = 0;
        
        while(cur0) break;//当cur数据>0时则表示该指针后的区间不存在符合条件的三元组
            //定义变量
            int left = cur+1;//left指针所在数据为cur指针后一个位置
            int right = nums.size()-1;
            
            int targe = -nums[cur];//变量targe用于存储cur所指数据的相反数,用来与左右数据之和进行比较

            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum > targe) --right;
                else if(sum < targe) ++left;
                else{
                    ret.push_back({nums[cur],nums[left],nums[right]});
                    ++left,--right;//存入一组数据之后应该继续遍历
                    
                    //对left,right指针进行去重
                    while(left