★ 算法OJ题 ★ 力扣15 - 三数之和

Ciallo～(∠・ω< )⌒☆ ~ 今天，芝麻凛将和大家一起做一道双指针算法题--三数之和~

目录

一  题目

二  算法解析

三  编写算法

一  题目

15. 三数之和 - 力扣（LeetCode）

二  算法解析

解法一：排序 + 暴力枚举 + 利用set去重

时间复杂度：O(N^3)

解法二：排序 + 双指针

• 排序；
• 固定一个数C（C <= 0）；
• 在该数后面的区间内，利用双指针算法，快速找两个数的和为 -C。

这道题⾥⾯需要有去重操作~

• 找到⼀个结果之后， left 和 right 指针要跳过重复的元素；
• 当使⽤完⼀次双指针算法之后，固定的 C 也要跳过重复的元素。

三  编写算法

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret; // 存放结果的顺序表~
        sort(nums.begin(), nums.end());  // 排序~
        int n = nums.size();
        // 固定数i
        for (int i = 0; i < n; ) // i的变化需要跳过相同的数，放后面写~
        {
            if (nums[i] > 0) // 小优化，三个大于0的数加起来不可能等于0~
                break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                // 两数之和
                int sum = nums[left] + nums[right];
                if (sum == target)
                {
                    ret.push_back({ nums[i], nums[left], nums[right] });
                    left++;
                    right--;
                    // 去重，left right 跳过相同数，但不能越界
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
                if (sum < target)
                    left++;
                if (sum > target)
                    right--;
            }
            i++;
            // 去重，i 跳过相同数，但不能越界
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};