leetcode：15. 三数之和

题目

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

示例：

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

解答 & 代码

写法一：

  1. class Solution {
  2. private:
  3.     // 双指针法求两数之和
  4.     // 返回数组中所有和为 target 的两个数，要求不能重复。传入的 nums 是升序数组
  5.     vector<vector<int>> twoSum(vector<int>& nums, int start, int end, int target)
  6.     {
  7.         vector<vector<int>> result;
  8.         int left = start;
  9.         int right = end;
  10.         while(left < right)
  11.         {
  12.             int leftNum = nums[left];
  13.             int rightNum = nums[right];
  14.             int sum = leftNum + rightNum;
  15.             if(sum < target)
  16.             {
  17.                 while(left < right && nums[left] == leftNum)
  18.                     ++left;
  19.             }
  20.             else if(sum > target)
  21.             {
  22.                 while(left < right && nums[right] == rightNum)
  23.                     --right;
  24.             }
  25.             else
  26.             {
  27.                 result.push_back({leftNum, rightNum});
  28.                 while(left < right && nums[left] == leftNum)
  29.                     ++left;
  30.                 while(left < right && nums[right] == rightNum)
  31.                     --right;
  32.             }
  33.         }
  34.         return result;
  35.     }
  36. public:
  37.     vector<vector<int>> threeSum(vector<int>& nums) {
  38.         vector<vector<int>> result;
  39.         int targetSum = 0;
  40.         // 1. 先排序
  41.         sort(nums.begin(), nums.end());
  42.         int firstIdx = 0;
  43.         // 2. 穷举第一个数
  44.         while(firstIdx < nums.size())
  45.         {
  46.             int first = nums[firstIdx];
  47.             // 2.1 targetSum - 第一个数，求两数之和
  48.             vector<vector<int>> twoSumResult = twoSum(nums, firstIdx + 1, nums.size() - 1, targetSum - first);
  49.             for(int i = 0; i < twoSumResult.size(); ++i)
  50.             {
  51.                 int second = twoSumResult[i][0];
  52.                 int third = twoSumResult[i][1];
  53.                 result.push_back({first, second, third});
  54.             }
  55.             // 跳过重复数字
  56.             while(firstIdx < nums.size() && nums[firstIdx] == first)
  57.                 ++firstIdx;
  58.         }
  59.         return result;
  60.     }
  61. };

复杂度分析：

  • 时间复杂度 O([中等] 15. 三数之和 - 图1)：
    • 数组排序时间复杂度 O(N logN)
    • 外层 while 循环遍历数组寻找第一个数 first，时间复杂度 O(N)；循环里调用 twoSumResult 用双指针法求两数之和，时间复杂度 O(N)。因此总体时间复杂度 O([中等] 15. 三数之和 - 图2)
  • 空间复杂度 O(N)：twoSumResult 存储两数之和的结果

执行结果：

  1. 执行结果：通过
  3. 执行用时：100 ms, 在所有 C++ 提交中击败了 28.65% 的用户
  4. 内存消耗：23.1 MB, 在所有 C++ 提交中击败了 11.28% 的用户

写法二：

[中等] 15. 三数之和