0

LeetCodeをはじめました。

さっそくですが、Two sumでエラーがでたので教えてほしいです。
まず、Brute Forceで下記コードを書きました。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(1,len(nums)):
                if(i==j):
                    continue
                elif(nums[j]==target-nums[i]):
                    return i,j

上記で実行させると、Time Limit Exceededのエラーとなってしまいました。
一見すると大丈夫そうに見えるのですが、何が問題でしょうか。

どなたかご教示お願いします。

4
  • そのコードですと組み合わせではなく順列になっていますので、最悪の場合で計算量が2倍になってしまいます。また、戻り値はリストのはずなので return [i, j] とすべきかと。
    – user39889
    Commented 2019年6月24日 15:49
  • ちなみに "Time Limit Exceeded" とは、制限時間を超えたという意味のエラーです。
    – Hideki
    Commented 2019年6月24日 20:22
  • 回答ありがとうございます。 戻り値をreturn [i,j]としましたが、同様に"Time Limit Exceeded"となってしまいました。 もっと時間がかからないようにしないといけないということでしょうか。。。
    – ken iwa
    Commented 2019年6月27日 2:42
  • 1
    例えば、wandbox.org/permlink/t4GPmKON62xRvtDd などの様にすると良いかも知れません。
    – user39889
    Commented 2019年6月27日 10:47

1 件の回答 1

1

そのコードを最小限修正するとしたら以下のようになるかと思います。問題となっている部分は内側のforが毎回リストの最初からループを回している部分です。内側はiの次の要素から処理をすればすべての組み合わせを処理できるので、range(1, len(nums))をrange(i+1, len(nums))に変更します。次にループの内側を手直しして完了です。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if(nums[j]==target-nums[i]):
                    return i,j

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。