4

http://www.leetcode.com/onlinejudgeで3Sumの問題を見つけました。これは次のようになります。

n個の整数の配列Sが与えられた場合、a + b + c = 0となるような要素a、b、cがSにありますか？ゼロの合計を与える配列内のすべての一意のトリプレットを見つけます。

注：トリプレット（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);
}

ご覧のとおり、これはすべての番号を取り、現在のインデックスの後に2つの番号が続きます。したがって、最初の正の数に達すると、役に立たないループを実行しているだけで、0に追加されるトリプレットは見つかりません。そこで、ソリューションを変更し、後に条件を追加しました。for

if (num[i] > 0)
    break;

事実上、これによりforループの実行回数が減り、解決策を見つけるのにかかる時間が短縮されます。これは、カウンターを追加して、ごとにインクリメントすることで確認しましたif()。COUNTER私の解決策のは、提案された解決策のカウンターよりも小さいたびに。

それでも、チェックページで変更したソリューションを入力すると、タイムアウトエラーが発生するか、変更されていないバージョンよりも時間がかかることが示されます。変更の何が問題になっているのか知りたいですか？

4

1 に答える 1

1

あなたのソリューションに問題はありません。ローカルでのソリューションと、条件がより速く実行される場合に追加されたソリューションの両方を試しました。System.nanotime()で時差を確認しました。ネットワークの問題により、ソリューション チェック ページでタイムアウト エラーが発生している可能性があります。

于 2012-05-24T07:37:37.663 に答える