60ms C++ solution similar to two sum


  • 5
    D

    The idea is to sort the vector, then do a linear time search for numbers that add up to the the negative of each number in the array in the remainder of the sorted array (so each step is similar to the two sum solution).

    As an optimization we can safely skip over numbers that are equal to the last number checked in the sorted vector (done via the do loops below).

    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            if (num.size() < 2) { return {}; }
            sort(num.begin(), num.end());
            vector<vector<int> > result; 
            int i = 0;
            while (i < num.size() - 2) {
                int target = -num[i];
                int j = i + 1, k = num.size() - 1;
                while (j < k) {
                    int value = num[j] + num[k];
                    if (value == target) {
                       result.emplace_back(vector<int>{num[i], num[j], num[k]});
                       do { j++; } while (j < k && num[j] == num[j - 1]);
                       do { k--; } while (j < k && num[k] == num[k + 1]);
                    } else if (value < target) {
                       do { j++; } while (j < k && num[j] == num[j - 1]);
                    } else {
                       do { k--; } while (j < k && num[k] == num[k + 1]);
                    }
                }
                do { i++; } while (i < num.size() - 2 && num[i] == num[i - 1]);
            }
            return result;
        }
    };

Log in to reply
 

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