LeetCode 15 —— 三数之和

1. 题目

2. 解题思路

首先我们对数组进行从小到大排序，然后遍历数组 $[0,nums.size()-3]$ 作为三元组中的 $a$，由于三元组的索引互不相同，所以余下的 $b$ 和 $c$ 我们则只能从 $a$ 后面的元素中取，而且 $b$ 和 $c$ 的索引也不能相同。

假设 $a$ 取的是第 $i$ 个元素，那么我们让 $b$ 首先指向第 $i+1$ 个元素， $c$ 首先指向第 $nums.size()-1$ 个也即最后一个元素。这时候，我们检查 $a+b+c$ 的和与零的关系。

• 如果二者正好相等，我们保存这个三元组，同时让 $b$ 向右移动一步，或者让 $c$ 向左移动一步；
• 如果和小于零，只能让 $b$ 向右移动一步；
• 如果和大于零，则只能让 $c$ 向左移动一步。

同时，结果中不能包含重复的三元组，所以 $a，b，c$ 更新的时候我们都要确保它们不与上一次的值相同。

排序的时间复杂度为 $O(nlogn)$，求和时，最外层遍历 $a$ 的时间复杂度为 $O(n)$，内层遍历 $b$ 和 $c$ 正好把数组访问一遍，时间复杂度也为 $O(n)$，所以求和的时间复杂度为 $O(n^2)$。所以，整体算法的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。

3. 代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > ret; 
        sort(nums.begin(), nums.end());
        int last = nums[0] - 1; // 上一个a，初始化为不和nums[0]相等即可
        for (int i = 0; i < nums.size()-2; ++i) {
            if (nums[i] == last) {
                continue;
            }
            int first = i + 1;
            int first_last_num = nums[first] - 1; // 上一个b，初始化为不和nums[first]相等即可
            int second = nums.size() - 1;
            int second_last_num = nums[second] + 1; // 上一个c，初始化为不和nums[second]相等即可
            while (first != second) {
                if (nums[first] == first_last_num) {
                    ++first;
                    continue;
                }
                if (nums[second] == second_last_num) {
                    --second;
                    continue;
                }
                int sum = nums[i] + nums[first] + nums[second];
                if (sum == 0) {
                    ret.push_back({nums[i], nums[first], nums[second]});
                    first_last_num = nums[first++]; // 更新上一次的b
                    second_last_num = nums[second]; // 更新上一次的c
                } else if (sum < 0) {
                    ++first;
                } else {
                    --second;
                }
            }
            last = nums[i]; // 更新上一次的a
        }
        return ret;
    }
};