题解 | #三数之和#

#include <unordered_set>
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        int n = num.size();

        if(n==0)
            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)
        // {
        //     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);
                
        //         if(c==a || c==b)
        //         {
        //             if(c==a)
        //             {
        //                 if(st[a]<2)
        //                     continue;

        //             }

        //             if(c==b)
        //             {
        //                 if(st[b]<2)
        //                     continue;
        //             }

        //             if(c==a && c==b)
        //             {
        //                 if(st[c]<3) continue;
        //             }

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

        //     }
        // }

        for(auto [a,y]:st)
        {
            for(auto [b,z]:st)
            {
                int c = -(a+b);
                if(a<=b && b<=c && st.count(c)>0)
                {
                    if(a==b && b==c && st[c]>=3)
                    {
                        ans.push_back({a,b,c});
                    }
                    if(a==b && b<c && st[a]>=2)
                    {
                        ans.push_back({a,b,c});
                    }
                    if(a<b && b==c && st[b]>=2)
                    {
                        ans.push_back({a,b,c});
                    }
                    if(a<b && b<c)
                    {
                        ans.push_back({a,b,c});
                    }
                }
            }
        }

        return ans;
        
    }
};

使用了map 但这样最后 时间复杂度是O(n^2logn)

之前用数组遍历没有通过 涉及去重的问题

vector<vector<int> > threeSum(vector<int> &num) {
        int n = num.size();

        if(n==0)
            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)
        {
            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;