My cpp code referenced soulmachin's code , got O(n^2) without Hashmap.


  • 1
    G
    class Solution {
    

    public:
    vector <vector <int>> threeSum (vector <int> &num) {
    vector <vector <int>> result;
    if (num.size() < 3) return result;

                sort (num.begin (), num.end ());
                 int target = 0;
    
                 auto last = num.end() ;
                 for (auto a = num.begin(); a < last; ++a) {
                        auto b = a + 1;
                        auto c = last - 1;
                        while (b < c) {
                                if ( *a + *b + *c < target) {
                                        ++b;
                                } else if ( *a + *b + *c  > target) {
                                        --c;
                                } else  {
                                        result.push_back({*a, *b, *c});
                                        ++b;
                                        --c;
                                }
                        }
                     /*  These word is edded by myself, is to accelerate. If NOT ADD, the code is TLE. */
                        while (*a == *(a+1)) {   // skip duplicate elsments 
                                ++a;
                        }
                 }
                 sort (result.begin(), result.end());
                 result.erase (unique (result.begin(), result.end()), result.end());
                 return result;
        }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.