题解 | #三数之和#

#include <cstddef>
#include <set>
#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @return int整型vector<vector<>>
     */


    vector<vector<int> > threeSum(vector<int>& num) {
        // write code here
        unordered_map<int, int> has;
        if (num.size() < 3) {
            return {};
        }
        for (int k = 0; k < num.size(); k++) {

            has[num[k]]++;
            // cout<<num[k]<<":"<<has[num[k]]<<" ";
        }

        vector<vector<int>>m;
        // sort(num.begin(), num.end());
        for (int i = 0; i < num.size(); i++) {
            for (int j = 1; j < num.size(); j++) {
                if (i != j) {
                    int n = num[i] + num[j];
                    // cout<<"i->"<<num[i]<<"j->"<<num[j]<<" -i-j-> "<<-n<<" ";
                    has[num[i]]--;
                    has[num[j]]--;
                    if (has[-n] > 0) {
                        cout << i << j << "i->" << num[i] << "j->" << num[j] << " -i-j-> " << -n << " ";
                        vector<int> S;
                        S.push_back(num[i]);
                        S.push_back(num[j]);
                        S.push_back(-n);
                        sort(S.begin(), S.end());
                        m.push_back(S);
                    }
                    has[num[i]]++;
                    has[num[j]]++;
                }

            }
        }
        set<vector<int>> uniqueSets(m.begin(), m.end());
        m.assign(uniqueSets.begin(), uniqueSets.end());
        return m;
    }
};

三数之和为0；首先 哈希表统计每个元素数量。

a+b+c=0; 令a+b=n， n=-c。 有多少种，a+b的组合，两层for循环。两层循环中i,j不能指向一个元素。 这样的a+b的组合找到之后，下面该怎么做？是不是如果可以在剩下的部分里面找到-n值就说明存在。如果表示剩下的部分，我们在unordered_map中，将i，j对应的值都减一，这样得到的是去掉一次a+b的其他元素数量。当-n的数量>1说明存在。此时这样的就是一种解。存vector<int> s; [num[i],num[j],-n]这就是一个解。但是需要有序 sort(S.begin(), S.end());之后再存入结果vector。 此时我们是在两层循环内部操作的，我们对(unordered_map中，将i，j对应的值都减一)这一步操作需要还原，等到ij变化后仍然是最原始的unordered_map。 最后仍然需要对结果vector去重。 先转set再转回去。