【LeetCode】Two Sumの解法

LeetCode - Two Sum

leetcode.com

解法。自分の場合は最初はv1（ブルートフォース）。 その次にv2（ハッシュ）、これで速度が100倍になった。 で、コメントをみてv3,finalです。

finalの場合、target - nums[i]をifの中で 計算しているようにしているが、ifがTrueになる確率の方が低いから、 変数への代入のコストが少なくてすむのだろう。 ちなみに enumerateを使おうが使わまいが、速度差はなかった。

あとは、towSum関数に直接コードかかないと30msくらい遅くなるが、 これは備忘録として見やすいようにしているだけ。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        return self.final(nums, target)


    def v1(self, nums, target):
        
        for i, n1 in enumerate(nums):
            for j, n2 in enumerate(nums[i+1:]):
                if n1 + n2 == target:
                    return [i, i+1+j]
        return None
    
    def v2(self, nums, target):
        map_ = {}
        for i,v in enumerate(nums):
            map_[v] = i
            
        for i, v in enumerate(nums):
            complement = target - v
            if (complement in map_) and (map_[complement] != i):
                return [i, map_[complement]]
            
        return None
    
    def v3(self, nums, target):
        map_ = {}
        for i, v in enumerate(nums):
            complement = target - v
            if complement in map_:
                return [i, map_[complement]]
            map_[v] = i
            
        return None
    
    def final(self, nums, target):
        map_ = {}
        for i in range(len(nums)):
            if target - nums[i] in map_:
                return (map_[target - nums[i]], i)
            map_[nums[i]] = i
        return None