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

c++ leetcode 三数之和

题目描述:

难度中等2433

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

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

一双指针法(最优解)

通过先进行排序之后,k 指向最小的元素i 指向下标为k + 1 的元素,j 指向最后一个元素(最大的元素);通过三个指向的元素相加,判断应该移动i 或者j; 三数相加> 0 ,j --; 三数相加<0 ;i++; 三数相加==0; 记录三数;i++,j–;避免重复, k 指向的元素如果大于零就直接退出循环(最小的元素都大于零没有必要找了);

class Solution {public:    vector
   
    
     > threeSum(vector
     
      & nums) {        vector
      
       
        > answer;        sort(nums.begin(),nums.end());        for (int k = 0; k < nums.size(); k++) {            int i = k + 1 ,j = nums.size() - 1;            if (k > 0 && nums[k] == nums[k - 1]) continue;            if (nums[k] > 0) break;            while (i < j) {                if (i > k + 1 && nums[i] == nums[i - 1]) { //避免重复的答案                    i += 1;                    continue;                }                 if (j < nums.size() - 1 && nums[j] == nums[j + 1]) {                    --j;                    continue;                }                if (nums[k] + nums[i] + nums[j] == 0) {                   vector
        
          temp; temp.push_back(nums[k]); temp.push_back(nums[i]); temp.push_back(nums[j]); answer.push_back(temp); i++; j--; }else if (nums[k] + nums[i] + nums[j] < 0) ++i; else if (nums[k] + nums[i] + nums[j] > 0) --j; } } return answer; } };
        
       
      
     
    
   

时空复杂度分析

时间复杂度: 移动k指针遍历一遍数组,(外层循环) 二指针遍历k + 1到 数组的末尾(一遍数组)(内层循环)

为O(N^2);

空间复杂度: 使用了额外的空间存储答案,可是答案不是随着数组的长度N变化的所以还是O(1);

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