Why my n^2 solution get TLE error?


  • 0
    Z
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int size = nums.size();
        
        if (size < 3)
            return ret;
        
        sort(nums.begin(), nums.end());
        
        for (int i = 0 ; i < size - 2; i++)
        {
            bool fl = false;
            bool fr = false;
            int l = i + 1;
            int r = size - 1;
            while ( l < r)
            {
                if (fr && nums[r] == nums[r+1] )
                {
                    r--;
                    continue;
                }
                if (fl && nums[l] == nums[l-1])
                {
                    l++;
                    continue;
                }
                if ((nums[i] + nums[l] + nums[r]) < 0)
                {
                    l++;
                    fl = true;
                }
                else if ((nums[i] + nums[l] + nums[r]) > 0)
                {
                    r--;
                    fr = true;
                }
                else
                {
                    vector<int> triplet(3, 0);
                    triplet[0] = nums[i];
                    triplet[1] = nums[l];
                    triplet[2] = nums[r];
                    ret.push_back(triplet);
                    l++;
                    r--;
                    fl = fr = true;
                }
            }
        }
        return ret;
    }

  • 0
    S

    What's your output when input is {0,0,0,0}? And the "sort()" is O(n^2) or O(n*lgn)?


Log in to reply
 

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