题目链接

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例

示例1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

提示

  • 0 <= nums.length <= 3000

  • -10 <= nums[i] <= 10

    思路

    排序+双指针

    首先想到的是暴力解法，即三重循环然后再去重，这样的做法开销会非常大。
    对于去重，我们可以先对数组进行排序，这样就保证了只会出现(a, b, c)一种顺序，从而减少重复。
    观察式子a + b + c = 0，当我们固定a时，b增大c就减小，一个递减一个递增，实际上就是双指针。
    另外，我们还可以进行一些特判：

  • 数组大小小于3，返回空数组

  • 对于排序后的数组，如果第一个数大于0，那么它之后的数都会大于0，最终的结果肯定不为0

    题解

    1. class Solution {
    2.  public:
    3.   vector<vector<int>> threeSum(vector<int> &nums) {
    4.       int n = nums.size();
    5.       if (n < 3) {
    6.           return {};
    7.       }
    8.       vector<vector<int>> ans;
    9.       sort(nums.begin(), nums.end());
    10.       for (int i = 0; i < n; ++i) {
    11.           if (nums[i] > 0) {
    12.               return ans;
    13.           }
    14.           if (i > 0 && nums[i - 1] == nums[i]) {
    15.               continue;
    16.           }
    17.           int left = i + 1, right = n - 1;
    18.           while (left < right) {
    19.               int sum = nums[i] + nums[left] + nums[right];
    20.               if (sum > 0) {  //和太大，移动右指针
    21.                   --right;
    22.               } else if (sum < 0) {
    23.                   ++left;
    24.               } else {
    25.                   ans.push_back(vector<int>{nums[i], nums[left], nums[right]});
    26.                   ++left;
    27.                   --right;
    28.                   while (left < right && nums[left - 1] == nums[left]) {
    29.                       ++left;
    30.                   }
    31.                   while (left < right && nums[right + 1] == nums[right]) {
    32.                       --right;
    33.                   }
    34.               }
    35.           }
    36.       }
    37.       return ans;
    38.   }
    39. };

    复杂度分析

  • 时间复杂度：0015-三数之和 - 图1，其中排序的复杂度为0015-三数之和 - 图2

  • 空间复杂度：0015-三数之和 - 图3，此为排序的空间复杂度，如果题目要求不能在原数组上修改，那么还需要保存副本，空间复杂度变为0015-三数之和 - 图4