Straightforward 104ms C++ solution based on 2sum and 3sum approach


  • 3
    D

    This is similar to the approach for 2sum and 3sum. The 2sum portion is solved via a linear time search. This search is done inside a quadratic time scan of the other two numbers in the sum, producing a n^3 algorithm overall. We can optimize by skipping over equal numbers in the array (done with the do loops).

    class Solution {
    public:
        vector<vector<int> > fourSum(vector<int> &num, int target) {
            if (num.size() < 4) { return {}; }
            vector<vector<int> > result;
            sort(num.begin(), num.end());
            int i = 0;
            while (i < num.size() - 3) {
                int j = i + 1;
                while (j < num.size() - 2) {
                    int two_sum_target = target - num[i] - num[j];
                    int k1 = j + 1, k2 = num.size() - 1;
                    while (k1 < k2) {
                        int value = num[k1] + num[k2];
                        if (value == two_sum_target) {
                            result.emplace_back(vector<int>{num[i], num[j], num[k1], num[k2]});
                            do { k1++; } while (k1 < k2 && num[k1] == num[k1 - 1]);
                            do { k2--; } while (k1 < k2 && num[k2] == num[k2 + 1]);
                        } else if (value < two_sum_target) {
                            do { k1++; } while (k1 < k2 && num[k1] == num[k1 - 1]);
                        } else {
                            do { k2--; } while (k1 < k2 && num[k2] == num[k2 + 1]);
                        }
                    }
                    do { j++; } while (j < num.size() - 2 && num[j] == num[j - 1]);
                }
                do { i++; } while (i < num.size() - 3 && 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.