本文共 1045 字，大约阅读时间需要 3 分钟。

15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

1. 用排序和双指针的方法完成。

• 先将数组由小到大排序（用sort函数即可）
• 从头到尾遍历数组，将遍历到的元素设为ass，这样这个问题就变成了在之后的元素中找到两个相加等于0-ass的元素。
• 将左指针置于遍历到的元素之后一个，右指针位于数组末尾。三数之和大于0即右指针移动，小于0即左指针移动。相等则存入数组。
• 注意：要避免重复的情况。在遍历过程中相等的数只遍历一次。找到目标的三个数存入数组时也要对左右指针做相同操作

class Solution {
   public:    vector
   
    
     > threeSum(vector
     
      & nums) {
           vector
      
       
         > res;        if(nums.size() < 3) return res;        sort(nums.begin(),nums.end());        for(int i=0;i
        
         =1 && nums[i]==nums[i-1]) continue; int ass=nums[i]; if(ass > 0) break; int left=i+1; int right=nums.size()-1; while(left < right){ if(ass + nums[left] + nums[right] < 0) left++; else if(ass + nums[left] + nums[right] > 0) right--; else{ res.push_back({ ass,nums[left],nums[right]}); left++; right--; while(left < right && nums[left]==nums[left-1]) left++; while(left < right && nums[right]==nums[right+1]) right--; } } } return res; }};
        
       
      
     
    
   

通过时间：

转载地址：http://hnemb.baihongyu.com/