LeetCode 练习题（简单1）

小A 和小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回小A 猜对了几次？

输入的guess数组为小A 每次的猜测，answer数组为小B 每次的选择。guess和answer的长度都等于3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/guess-numbers

个人答案（python）：

 1 class Solution(object):
 2     def game(self, guess, answer):
 3         """
 4         :type guess: List[int]
 5         :type answer: List[int]
 6         :rtype: int
 7         """
 8         num = 0 
 9         for i in range(len(guess)):
10             if (guess[i] == answer[i]):
11                 num += 1
12             i+=1
13         return num

其他人的答案：

return sum(guess[i]==answer[i] for i in range(len(guess)))

　　2. 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

　　　你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

　　　来源：力扣（LeetCode）
　　　链接：https://leetcode-cn.com/problems/two-sum

个人答案：遍历数组a,然后看除了a数组中有没有target-a的数,这样就能保证该数组有两个数和等于target;但是时间复杂度为$O(n^2)$;

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

其他答案：

可以借用哈希(python叫字典),我们遍历元素的时候,且记录元素的下标,当我们找target-a时候,只需要在字典找,就可以了,查找字典时间复杂度为$O(1)$

所以,

时间复杂度:$O(n)$

空间复杂度:$O(n)$

class Solution(object):
    def twoSum(self, nums, target):

        n = len(nums)
        lookup = {}
        for i in range(n):
            tmp = target - nums[i]
            if tmp in lookup:
                return [lookup[tmp],i]
            lookup[nums[i]] = i