c++ leetcode 三数之和

题目描述:

15. 三数之和

难度中等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<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> 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<int> 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);