LeetCode：1.两数之和

chaoxi.jpg

题目：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题解:

1.暴力破解brute force

# 思路1:brute force, 强搞!!!
#     使用两个for循环嵌套,注意不能使用相同的index
#     时间:O(n^2)  空间:O(1)
from typing import List

class Solution(object):
  def twoSum(self, nums:List[int], target:int) -> List[int]:
    for i in range(len(nums)):
      for j in range(i+1, len(nums)):
        if nums[i]+nums[j] == target:
          return [i, j]
    return None
    
s1 = Solution()
s1.twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9], 10)

执行结果：通过

显示详情

执行用时 :7680 ms, 在所有 Python3 提交中击败了5.03%的用户

内存消耗 :14.3 MB, 在所有 Python3 提交中击败了21.95%的用户

2.cache存储

# 思路2:cache存储
#     用cache存储需要找寻的值,因为我们需要返回index索引
#     时间:O(n)  空间:O(n)
from typing import List

class Solution(object):
    def twoSum(self, nums:List[int], target:int) -> List[int]:
        cache = dict()
        for idx, num in enumerate(nums):
            cur = target-num
            if num in cache:
                return [cache[num], idx]
            cache[cur] = idx
        return None

s1 = Solution()
s1.twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9], 10)

执行结果：通过
显示详情
执行用时 :64 ms, 在所有 Python3 提交中击败了54.08%的用户
内存消耗 :15.1 MB, 在所有 Python3 提交中击败了5.48%的用户

        # 另一种写法
        # cache = dict()
        # for idx, num in enumerate(nums):
        #     if num in cache:
        #         return [cache[num], idx]
        #     else:
        #         cache[target-num] = idx

执行结果：通过
显示详情
执行用时 :40 ms, 在所有 Python3 提交中击败了90.03%的用户
内存消耗 :15.2 MB, 在所有 Python3 提交中击败了5.48%的用户