15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

---

给定一串无序的数组，找出所有不重复的三元组，其和为0。其实就是三个数加起来等于某个特定的数，这和两个数加起来等于某个特定的数是类似的。 暴力求解肯定不行$O(n^3)$。后来想到hash，把所有数hash，然后任取两个数a,b，然后查hash表，如果-(a+b)在hash表中，则找到一个三元组，此时的时间复杂度是$O(n^2)$。 完整代码如下：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        set<vector<int> > tmp;
        int min_v = INT_MAX, max_v = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < min_v) {
                min_v = nums[i];
            }
            if (nums[i] > max_v) {
                max_v = nums[i];
            }
        }
        vector<int> hash(max_v – min_v + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i] – min_v]++;
        }
        for (int i = 0; i < hash.size(); i++) {
            if (hash[i] == 0)
                continue;
            hash[i]–;
            for (int j = i; j < hash.size(); j++) {
                if (hash[j] == 0)
                    continue;
                hash[j]–;
                int sum1 = i + min_v + j + min_v;
                int idx = -sum1 – min_v;
                if (idx >= 0 && idx < hash.size() && hash[-sum1 – min_v]) {
                    vector<int> hit = { i + min_v, j + min_v, -sum1 };
                    sort(hit.begin(), hit.end());
                    tmp.insert(hit);
                }
                hash[j]++;
            }
            hash[i]++;
        }
        vector<vector<int> > ans;
        for (auto const& vi : tmp) {
            ans.push_back(vi);
        }
        return ans;
    }
};

本代码提交AC，用时108MS，排在了倒数3%的位置，说明算法还有待改进。

上述代码有两个地方值得改进。首先，每个三元组我都重新排序了，因为a,b是任意取的，导致-(a+b)的大小关系和a,b不确定，我们可以先选定a，然后等价于找两个数加起来等于-a，找的方法就是从比a大的那边找，并且b和c分别是比a大的那边的首尾指针，这样就确定了a<b<c的关系，不用担心有遗漏情况，因为如果有比a小的两个数b,c和a加起来等于0，那么在外层遍历b或c的时候就已经找到了。
第二个可改进的地方是，因为上述策略不会导致有重复的三元组出现，所以set操作也可以省略了。第二版代码如下：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        vector<vector<int> > tmp;
        if (nums.size() < 3)
            return tmp;
        int min_v = INT_MAX, max_v = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < min_v) {
                min_v = nums[i];
            }
            if (nums[i] > max_v) {
                max_v = nums[i];
            }
        }
        vector<int> hash(max_v – min_v + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i] – min_v]++;
        }
        for (int i = 0; i < hash.size(); i++) {
            if (hash[i] == 0)
                continue;
            hash[i]–;
            int s = i, t = hash.size() – 1;
            while (s <= t) {
                if (!hash[s]) {
                    s++;
                    continue;
                }
                else {
                    hash[s]–;
                }
                if (!hash[t]) {
                    t–;
                    hash[s]++;
                    continue;
                }
                else {
                    hash[t]–;
                }
                int sum1 = s + min_v + t + min_v;
                hash[s]++;
                hash[t]++;
                if (sum1 + i + min_v < 0) {
                    s++;
                }
                else if (sum1 + i + min_v > 0) {
                    t–;
                }
                else {
                    vector<int> hit = { i + min_v, s + min_v, t + min_v };
                    tmp.push_back(hit);
                    s++;
                    t–;
                }
            }
            hash[i]++;
        }
        return tmp;
    }
};

本代码提交AC，用时52MS，瞬间排在了前20%。
其实可以直接对数组排序来代替我的hash，渐进复杂度都是一样的。

二刷：
上面的代码太复杂了，简洁的做法是，先对数组排序，然后找a<b<c使得a+b+c=0，我们用i,j,k分别指向要找的a,b,c，外层循环是i尝试每个数，内存循环是在i右边的首尾指针j和k，找a[j]+a[k]=-a[i]的(j,k)对。内存循环相当于常规的2sum了。
注意要对i,j,k进行去重。完整代码如下，超简洁。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int> > ans;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i – 1])
                continue; // avoid duplicates
            for (int j = i + 1, k = n – 1; j < k;) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    ans.push_back({ nums[i], nums[j], nums[k] });
                    ++j;
                    –k;
                    while (j < k && nums[j] == nums[j – 1])
                        ++j; // avoid duplicates
                    while (j < k && nums[k] == nums[k + 1])
                        –k; // avoid duplicates
                }
                else if (nums[i] + nums[j] + nums[k] > 0) {
                    –k;
                }
                else {
                    ++j;
                }
            }
        }
        return ans;
    }
};

本代码提交AC，用时118MS。

三刷。更简单的借助hash的O(n^2)解法，hash里存储了每个数出现的次数。为了避免重复，特别需要注意nums[i]!=nums[i-1]；nums[j]!=nums[j-1]；且对于第三个数another，它要大于nums[j]，且存在。所以这里面的数值关系是nums[i]<nums[j]<another，这样才能避免三元组重复。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        unordered_map<int, int> hash;
        for(int i = 0; i < n; ++i) ++hash[nums[i]];
        for(int i = 0; i < n; ++i) {
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            
            --hash[nums[i]];
            for(int j = i + 1; j < n; ++j) {
                if(j != i + 1 && nums[j] == nums[j - 1]) continue;
                
                --hash[nums[j]];
                int another = - nums[i] - nums[j];
                if(another >= nums[j] && hash[another] > 0) ans.push_back({nums[i], nums[j], another});
                ++hash[nums[j]];
            }
            ++hash[nums[i]];
        }
        return ans;
    }
};

本代码提交AC，用时800MS，效率较低。

四刷。先排序，然后固定一个数i，另外两个数j,k分别指向i右边的数组的头尾，头尾指针移动的方法找加和等于-nums[i]的数。需要对i/j/k都while去重。完整代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        vector<vector<int>> ans;
        int n = nums.size();
        int i = 0;
        while(i < n - 2) {
            if(i != 0 && nums[i] == nums[i - 1]) {
                ++i;
                continue;
            }
            int target = -nums[i];
            int j = i + 1, k = n - 1;
            while(j < k) {
                if(nums[j] + nums[k] == target) {
                    vector<int> tmp = {nums[i], nums[j], nums[k]};
                    ans.push_back(tmp);
                    while(j < k && nums[j] == tmp[1]) ++j;
                    while(j < k && nums[k] == tmp[2]) --k;
                } else if (nums[j] + nums[k] > target) {
                    --k;
                } else {
                    ++j;
                }
            }
            ++i;
        }
        return ans;
    }
};

本代码提交AC，用时124MS，比用hash的方法快很多。