Three Sum

15. 三数之和

分析

排序数组：
- 首先将数组从小到大排序，方便后续操作
固定一个数，双指针搜索：
- 遍历排序后的数组，用 i 指向当前固定的数
- 在 i 的右侧，使用双指针 j 和 k：
  - j 指向 i + 1
  - k 指向数组末尾
- 检查三数之和：
  - 若三数之和小于 0，说明需要更大的值，移动 j 向右
  - 若三数之和大于 0，说明需要更小的值，移动 k 向左
  - 若三数之和等于 0，记录结果，同时移动 j 和 k 跳过重复值
去重：
- 对于固定数 nums[i]，若 nums[i] = nums[i-1]，跳过当前遍历，避免重复三元组
- 对于 nums[j] 和 nums[k]，在找到一个解后，继续移动跳过相同值

时间复杂度

排序复杂度：O(nlogn)
三重循环复杂度：外层循环 O(n)，内层双指针 O(n)，总复杂度为 O(n^2)

总时间复杂度 O(n^2)

空间复杂度

使用排序 O(logn) 的额外空间，其余操作在原地完成，空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        std::vector<std::vector<int>> res;
        std::sort(nums.begin(), nums.end()); // 对数组进行排序

        for (int i = 0; i < nums.size(); ++i)
        {
            // 跳过重复的固定数
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // 双指针寻找其他两数
            for (int j = i + 1, k = nums.size() - 1; j < k; ++ j)
            {
                // 跳过重复的第二个数
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                // 移动右指针，寻找满足条件的三元组
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) -- k;

                // 判断当前三数之和是否为零
                if (nums[i] + nums[j] + nums[k] == 0)
                    res.push_back({nums[i], nums[j], nums[k]});
            }
        }

        return res;
    }
};