share my C++ n^2 solution


  • 0
    N

    First, sort the array, then if the first num is fixed, 3Sum Problem is simplified to 2Sum(could be solved in O(n) time using two pointers).

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> ret;
            sort(nums.begin(), nums.end());
            for (int i = 0; i < nums.size(); ++ i){
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                int j = i + 1,  k = nums.size() - 1;
                if (nums[i] + nums[j] > 0) break;
                while (j < k){
                    if (j > i + 1 && nums[j] == nums[j - 1]){
                        j ++;
                        continue;
                    }
                    while (k >= j && nums[i] + nums[j] + nums[k] > 0)
                        k --;
                    if (j < k && nums[i] + nums[j] + nums[k] == 0){
                        ret.push_back(vector<int>(3, 0));
                        ret[ret.size() - 1][0] = nums[i];
                        ret[ret.size() - 1][1] = nums[j];
                        ret[ret.size() - 1][2] = nums[k];
                    }
                    j ++;
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

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