《算法面试通关40讲》笔记

leetcode 15 - 3sum

要点

首先，和是确定的，可以降低一个自由度，从 $n^3$ 降低到 $n^2$ ；
其次，排序的复杂度是，经过排序，只要遍历第一个维度，剩下的两个维度之和是确定的；
1. 如果是普通的2sum问题，可以用一个哈希表来解决，遍历一个维度的复杂度是 $n$ ，查找对应值的复杂度为 $1$ ；
2. 但由于3sum中的不同2sum问题是不同的，所以才要排序；基于排序，可以将复杂度从嵌套遍历 $n^2$ ，变成从两边向中间靠近的线性复杂度，最终结果的复杂度就是 $n^2 log(n)$ ，做法是：取左右两端之和，大了就使大值往小的方向取，小了就使小值往大的方向取。
3. 另外，经过排序，如果在遍历中发现当前元素和前一个元素相同，那么可以跳过了，因为如果当前元素即便有解，结果也和之前得到的结果一样。

代码

class Solution {
public:
    static vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (unsigned i = 0, size = nums.size(); i < size; ++i) {
            if (i > 0 && nums[i-1] == nums[i]) continue;
            twoSumWithTarget(nums, i + 1, size - 1, -nums[i], result);
        }
        return result;
    }
    static void twoSumWithTarget(vector<int>& nums, unsigned l, unsigned r, int target, vector<vector<int>>& result) {
        while (l < r) {
            auto lVal = nums[l], rVal = nums[r];
            auto lrValSum = lVal + rVal;
            if (lrValSum == target) {
                vector<int> subResult{lVal, rVal, -target};
                result.emplace_back(subResult);
                while (l < r && lVal == nums[l+1]) ++l;
                while (l < r && rVal == nums[r-1]) --r;
            }
            if (lrValSum < target) ++l;
            else --r;
        }
    }
};