3etum LTE leetcode

Question

我正在做3sum問題在leetcode.com

蠻力的時間複雜度是O（N^3）。

我使用哈希表，所以我認爲時間複雜度是O（N^2）。

然而，我仍然有一個TLE（超出時間限制）

我怎樣才能加快我的代碼？

以下是我的代碼

非常感謝！

class Solution public: 
vector<vector<int>> threeSum(vector<int>& nums) { 

    vector<vector<int>> ANS; 
    if(nums.size() < 3) return ANS; 

    map<int,int*> hashtable; 
    map<int,int*>::iterator it; 
    vector<int> ans; 

    for(int i=0;i < nums.size();i++) 
    { 

     for(int j=i+1;j < nums.size();j++) 
     { 

      it = hashtable.find(nums[j]); 
      if(it != hashtable.end()) //found target 
      { 
       ans.push_back(nums[j]); 
       ans.push_back((it)->second[0]); 
       ans.push_back((it)->second[1]); 
       sort(ans.begin(),ans.end()); 
       ANS.push_back(ans); 

       ans.clear(); 

      } 
      else 
      { 
       int* temp = new int[2]; 
       temp[0]=nums[i]; 
       temp[1]=nums[j]; 
       hashtable[0-nums[i]-nums[j]]=temp; 

      } 
     } 
     hashtable.clear(); 

    } 
    sort(ANS.begin(), ANS.end()); 
    ANS.erase(unique(ANS.begin(), ANS.end()), ANS.end()); 
    return ANS; 
}}; 

Answer 1

您的解決方案是不是真的O(n^2)，它肯定比O(n^2)昂貴。而在沒有任何優化的O(n^2)解決方案將不會通過OJ。這是我的解決方案，它是O(n^2)。我已經在代碼中加入瞭解釋的評論。

vector<vector<int> > threeSum(vector<int> &num) { 
    vector <vector<int> > result; 
    size_t n = num.size(); 
    if(n < 3) return result; 

    vector<int> solution(3); 
    sort(num.begin(), num.end()); 
    for(int i = 0; i < n - 2; ++i) { 
     int start = i + 1, end = n - 1; 

     while(start < end) { 
      int sum = num[start] + num[end] + num[i]; 
      if(sum == 0) { 
       solution.at(0) = num[i]; 
       solution.at(1) = num[start]; 
       solution.at(2) = num[end]; 
       result.push_back(solution); 
       // these loops will skip same elements and fasten the algorithm 
       // while(start < n - 1 and num[start] == num[start + 1]) start++; 
       // while(end > i + 1 and num[end] == num[end - 1]) end--; 
       start++, end--; 
      } else if(sum > 0) { 
       // while(end > i + 1 and num[end] == num[end - 1]) end--; 
       end--; 
      } else { 
       // while(start < n - 1 and num[start] == num[start + 1]) start++; 
       start++; 
      } 
     } 
     while(i < n - 1 and num[i] == num[i + 1]) i++; 
    } 

    return result; 
} 

讓我知道你是否有任何問題。希望能幫助到你！