LC001 Two Sums

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My Solution 1 暴力:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        xpo=0        
        for x in nums:
            ypo=xpo+1
            ylist=nums[ypo:]
            for y in ylist:
                if x+y == target:
                    return (xpo,ypo)
                ypo += 1
            xpo += 1
            

Result:

Runtime: 5088 ms, faster than 19.20% of Python3 online submissions for Two Sum.
Memory Usage: 13.5 MB, less than 52.60% of Python3 online submissions for Two Sum.

My Solution 2 Two-pass Hash Table:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        thisdict={}
        indexnum=0
        indexnum2=0
        for i in nums:
            thisdict[i] = indexnum
            indexnum+=1
        for i in nums:
            if target-i in thisdict and indexnum2!= thisdict[target-i] :
                return (indexnum2, thisdict[target-i])
            indexnum2+=1

Result:

Runtime: 40 ms, faster than 80.37% of Python3 online submissions for Two Sum.
Memory Usage: 14.9 MB, less than 5.08% of Python3 online submissions for Two Sum.