1. Two Sum

这个题过于经典，是个easy题型，但是因为在3sum之前想复习一下所以先写一下思路。

首先这个followup看完就知道一开始肯定是有brute force解法的，两次for循环找到相加为target的就直接返回

现在我们看看如何能够不用两个for-loop。

首先就是我们需要找到两个数相加 = target，但是其实我们也可以反向想一下，只要找到一个数 = target - 另一个数就可以了

比较简单的想法是我们循环两次，第一次保存target-nums[i]，第二次循环来寻找数列是否有一个数 = target-nums[i]且这个数的i不等于nums[i]的 i，否则可能会造成target=某个数的2倍数时找到同一位置的这个数两次。（ex. [3,3] target = 6)

hashmap%2520%253D%2520%257B%257D%250A%250Afor%2520i%2520in%2520range(len(nums))%253A%250A%2520%2520%2520%2520hashmap%255Bnums%255Bi%255D%255D%2520%253D%2520i%250A%250Afor%2520i%2520in%2520range(len(nums))%253A%250A%2520%2520%2520%2520complement%2520%253D%2520target%2520-%2520nums%255Bi%255D%250A%2520%2520%2520%2520if%2520complement%2520in%2520hashmap%2520and%2520hashmap%255Bcomplement%255D%2520!%253D%2520i%253A%250A%2520%2520%2520%2520%2520%2520%2520%2520return%2520%255Bi%252C%2520hashmap%255Bcomplement%255D%255D%250A%250A%2523%2520If%2520no%2520valid%2520pair%2520is%2520found%252C%2520return%2520an%2520empty%2520list%250Areturn%2520%255B%255D

hashmap = {}

for i in range(len(nums)):
    hashmap[nums[i]] = i

for i in range(len(nums)):
    complement = target - nums[i]
    if complement in hashmap and hashmap[complement] != i:
        return [i, hashmap[complement]]

# If no valid pair is found, return an empty list
return []

Python

而如果我们一个for-loop可以循环自身，同时又用 $O(1)$ 的方式找到之前循环过的数字是否 = target - 自身，那么我们就用一个for loop就可以直接返回这个pair了

题目里的Only One Valid answer exists就很重要，因为有且只有一对，所以找到之后马上返回是没问题的。并不会出现找不到or重复的问题。

用 $O(1)$ 方式找数字非常容易想到hash table因为key的保存是hash，查表的时候只需要O(1)

所以具体Code如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return (i, dic[target-num])
            dic[num] = i

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return (i, dic[target-num])
            dic[num] = i

Python

1. Two Sum

文章评论