

LeetCodeをはじめました。

さっそくですが、[Two sum](https://leetcode.com/problems/two-sum/)でエラーがでたので教えてほしいです。  
まず、Brute Forceで下記コードを書きました。

[code]

    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
    
[/code]

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

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


CC BY-SA 4.0
2019-06-24T15:04:32.367
56070
2019-08-04T04:16:33.577
2019-06-25T00:23:08.507
3060
34849
question
python アルゴリズム
LeetCodeでBrute ForceするとTime Limit Exceededする


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

[code]

    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
    
[/code]


CC BY-SA 4.0
2019-08-04T04:16:33.577
57150
2019-08-04T04:16:33.577
459
56070
answer