题解 | #三数之和#

class Solution {
  public:
    // 官解 效率更高的 双指针法
    vector<vector<int> > threeSum(vector<int>& num) {
        int n = num.size();

        if (n <= 2)
            return {};

        vector<vector<int>> ans;
        // 对数组排序
        sort(num.begin(), num.end());
        unordered_map<int, int> st;
        // map<int, int> st;
        for (int i = 0; i < n; ++i) {
            st[num[i]]++;
        }
        int prea = 101, preb = 101, prec = 101;
        for (int i = 0; i < n; ++i) {
            if(i>0 && num[i]==num[i-1]) // 关键！
                continue;
            for (int j = i + 1; j < n; ++j) {
                int a = num[i];
                int b = num[j];
                // if(st[a]<=0 || st[b]<=0)
                //     continue;
                int c = -(a + b);

                int t = st.count(c);
                if (a <= b && b <= c && t > 0) {
                    if (a == prea && b == preb)
                        continue;
                    if (a == b && b == c && st[c] >= 3) {
                        ans.push_back({a, b, c});
                        prea = a;
                        preb = b;
                        prec = c;
                    }

                    if (a == b && b < c && st[a] >= 2) {
                        ans.push_back({a, b, c});
                        prea = a;
                        preb = b;
                        prec = c;
                    }

                    if (b == c && a < b && st[c] >= 2) {
                        ans.push_back({a, b, c});
                        prea = a;
                        preb = b;
                        prec = c;
                    }

                    if (a < b && b < c) {
                        ans.push_back({a, b, c});
                        prea = a;
                        preb = b;
                        prec = c;
                    }
                }

            }
        }

        return ans;
    }
};

我在自己方法 增加一个去重就通过了

O（n2） O（n）