Why is "Time Limit Exceeded" got


  • 0
    J

    Dear sirs,
    my code for 3sum is shown bellow, and the when I submit my code, I get the Time Limit Exceeded error with input example,

    [7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6]

    But I am quite confused; could anyone help?
    ...
    #include <iostream> // std::cout
    #include <algorithm> // std::find
    #include <vector> // std::vector

    class Solution {
    public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    std::sort (nums.begin(), nums.end());
    vector<int> tmpv;
    vector<vector<int>> finalv;
    tmpv.clear();

         for(int i = (nums.size() -1) ;i>0;i--){
             for(int j=0;j<i;j++){
                 int part = nums[i] + nums[j];
                 if(((part*(-1)) >= nums[j]) && ((part*(-1)) <= nums[i]) ) {
                   //printf("\n i: %d, j:%d, part: %d\n",i,j,part*(-1));
                   vector<int>::iterator it1= nums.begin();
                   vector<int>::iterator it2=nums.begin();
                   std::advance(it1, j+1);
                   std::advance(it2, i);
                   if(std::find( it1, it2 ,(part*(-1)) ) != it2){
                     
                       tmpv.clear();
                       tmpv.push_back(nums[j]);
                       tmpv.push_back(part*(-1));
                       tmpv.push_back(nums[i]);
                       //check isexist
                       if(std::find(finalv.begin(),finalv.end(),tmpv)==finalv.end())
                           finalv.push_back(tmpv);
                   }                   
                 }
                 else{
    
                     continue;
                 }
    
                   
             }
         }
         return finalv;
    }
    

    };


  • 0
    J

    Let me do the eyes good.

    #include <iostream>     // std::cout
    #include <algorithm>    // std::find
    #include <vector>       // std::vector
    
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
             std::sort (nums.begin(), nums.end());
             vector<int> tmpv;
             vector<vector<int>> finalv;
             tmpv.clear();
      
             for(int i = (nums.size() -1) ;i>0;i--){
                 for(int j=0;j<i;j++){
                     int part = nums[i] + nums[j];
                     if(((part*(-1)) >= nums[j]) && ((part*(-1)) <= nums[i]) ) {
                       //printf("\n i: %d, j:%d, part: %d\n",i,j,part*(-1));
                       vector<int>::iterator it1= nums.begin();
                       vector<int>::iterator it2=nums.begin();
                       std::advance(it1, j+1);
                       std::advance(it2, i);
                       if(std::find( it1, it2 ,(part*(-1)) ) != it2){
                         
                           tmpv.clear();
                           tmpv.push_back(nums[j]);
                           tmpv.push_back(part*(-1));
                           tmpv.push_back(nums[i]);
                           //check isexist
                           if(std::find(finalv.begin(),finalv.end(),tmpv)==finalv.end())
                               finalv.push_back(tmpv);
                       }                   
                     }
                     else{
    
                         continue;
                     }
    
                       
                 }
             }
             return finalv;
        }
    };

  • 0
    H

    You have two for loops, one for i and one for j this is O(n^2).
    then you do a std:find in an if statement, this makes your code O(n^3).


Log in to reply
 

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