3Sum兩種相似算法的區別？

我發現3Sum問題上http://www.leetcode.com/onlinejudge出外下面：3Sum兩種相似算法的區別？

給定n個整數的數組S，在那裏元件A，B，C在S，從而使A + B + C = 0？查找數組中所有唯一的三元組，它們的總和爲零。

注：三元組（a，b，c）中的元素必須是非降序。（即a≤b≤c）解決方案集不能包含重複的三元組。

For example, given array S = {-1 0 1 2 -1 -4}, 

A solution set is: 
(-1, 0, 1) 
(-1, -1, 2)

我通過該網站去，發現這個建議的解決方案：

public ArrayList<ArrayList<Integer>> threeSum(int[] num) { 
    Arrays.sort(num); 
    HashSet<ArrayList<Integer>> lstSoln = new HashSet<ArrayList<Integer>>(); 

    ArrayList<Integer> tempArr = null; 
    for (int i = 0; i < num.length; i++) { 
     int j = i + 1; 
     int k = num.length - 1; 
     while (j < k) { 
      int sum3 = num[i] + num[j] + num[k]; 
      if (sum3 < 0) { 
       j++; 
      } else if (sum3 > 0) { 
       k--; 
      } else { 
       tempArr = new ArrayList<Integer>(); 
       Collections.addAll(tempArr, num[i], num[j], num[k]); 
       lstSoln.add(tempArr); 
       j++; 
       k--; 
      } 
     } 
    } 

    return new ArrayList<ArrayList<Integer>>(lstSoln); 
}

正如你所看到的，這需要每一個數字，然後與目前指數經過兩數如下。所以，這是很明顯，一旦達到第一個正數，我們只是在做無用的循環，我們不會找到任何三重添加到0。所以我修改瞭解決方案和for

if (num[i] > 0) 
    break;

後添加的條件

實際上，這應該會降低for循環的運行次數，從而減少找到解決方案所需的時間。我甚至通過增加一個計數器並在每個if()增加它來檢查。每次我的解決方案的COUNTER都小於建議解決方案的計數器。

但是，當我在那裏檢查頁面輸入修改後的解決方案時，它會導致超時錯誤或者顯示的時間超過未修改的版本！我想知道我的修改有什麼問題嗎？

來源

2012-05-24 inquizitive

您的解決方案是否有可能在判斷超出時間限制之前執行更多測試用例，因此顯示更高的值？你的確更好。而FYI，如果我們不考慮32位整數限制，則3SUM的下界爲O（n^2）。 – Haozhun

我沒有看到你的解決方案有什麼問題，我試了兩個解決方案在我的本地和添加條件運行速度更快。我使用System.nanotime（）檢查了時差。由於網絡問題，您可能在解決方案檢查頁面上遇到超時錯誤。

來源

2012-05-24 07:37:37 coder

起初我甚至都認爲是一樣的，但是後來我用多次修改和未修改的版本進行了多次檢查，結果都差不多。據他們說，未修改的運行速度更快。即使在使用System.nanoTime（）的我的電腦中，我的顯然應該是更快。 – inquizitive

3Sum兩種相似算法的區別？

回答

相關問題