力扣-1-两数之和

1. 两数之和 - 力扣（LeetCode）

核心：以空间换时间

from typing import List

class Solution(object):
    """
     类似双重循环的暴力解
     但是内部循环切除了前面已经遍历过的
     比如说 目标为 7，前面两个数字为 4，2，……
     第一次循环已经判断 4 + 2 != 7了
     第二次从 2 开始遍历，就不用从头开始，再计算一遍 2 + 4了
    """
    def twoSum1(self, nums, target):
        # 遍历列表
        for i in range(len(nums)):
            # 计算需要找到的下一个目标数字
            res = target-nums[i]
                # 遍历剩下的元素，查找是否存在该数字
            if res in nums[i+1:]:
                # 若存在，返回答案。这里由于是两数之和，可采用.index()方法
                # 获得目标元素在nums[i+1:]这个子数组中的索引后，还需加上i+1才是该元素在nums中的索引
                return [i, nums[i+1:].index(res)+i+1]
                # i是当前元素坐标
                # nums[i+1:].index(res)是从当前元素往后的切片生成的新数组中，res的索引，从0开始
                # 最后得到的应该是在原来数组中的索引，所以要 +i+1
    """
     时间复杂度为O(n)的解
     我的一开始的疑惑是，在字典中用 in 搜索，不和list中一样吗
     但其实字典采用的是Hash结构，在存储键值对 k-v时，会对k进行hash散列得到一个内存地址，将v存入
     使用 in 搜索时，也是对关键字进行hash散列，直接去得到的地址中取值，若不为空则找到
     故此时间复杂度为O(1)
    """
    def twoSum2(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i in range(len(nums)):
            c = target - nums[i]
            if c in d: return [d[c], i]
            d[nums[i]] = i
        return []

    """
    稍微简化了第二段代码
    使用了enumerate(nums)
    enumerate 是 Python 中一个非常有用的内置函数，
    它用于在遍历可迭代对象（如列表、元组、字符串等）时同时获取元素的索引和值。
    """
    def twoSum3(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for index, num in enumerate(nums):
            c = target - num
            if c in d: return [d[num], index]
            d[num] = index
        return []