在原始森林

题目

https://leetcode.cn/problems/two-sum/

给定一个整数数组 nums 和一个整数 target ，返回两个数字的索引，使得它们加起来等于 target。
可以假设每个输入都只有一个解 ，并且不能使用同一个元素两次。
可以按任意顺序返回答案。

自解

暴力枚举

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 target == nums[i]+nums[j]:
                    return i,j
        return []

第一道题，学如何用 for 循环遍历数组。

哈希表（两次迭代） ^a89bdc

在第一次迭代中，将每个元素的值作为键，其索引作为值添加到哈希表中。

在第二次迭代中，检查每个元素的补集（ $target−nums[i]$）是否存在于哈希表中。如果存在，则返回当前元素的索引及其补集的索引。

迭代是指重复执行一段代码的过程，通常是为了遍历某个集合（比如数组、列表）中的每一个元素。

def twoSum(self, nums: List[int], target: int) -> List[int]:
    harshtable=dict()
    for i in range(len(nums)):
        harshtable[nums[i]]=i
    for i in range(len(nums)):
        comp=target-nums[i]
        if comp in harshtable and harshtable[comp]!=i:
            return i,harshtable[comp]

第一次用晕乎乎，不知道哈希表是什么，还把键和值弄反了。

哈希表（一次迭代）

在遍历哈希表并向其中插入元素的之前，回溯检查当前元素的补集是否已存在于哈希表中。如果存在，我们就找到了解决方案，并立即返回索引。

def twoSum(self, nums, target):
    harshtable=dict()
    for i,num in enumerate(nums):
        comp = target - num
        if comp in harshtable:
            return i,harshtable[comp]
        harshtable[num]=i
    return []

内置函数 enumerate 在 for 循环中可以分别得到数组的索引和值。dict 用于创建一个字典。

题解

灵茶山艾府

和官方题解的哈希表差不多，图解会更直观。

def twoSum(self, nums, target):
    harshtable=dict()
    for i,num in enumerate(nums):
        if target-num in harshtable:
            return i,harshtable[target-num]
        harshtable[num]=i
    return []

总结：使用哈希表可以以牺牲空间为代价，降低时间复杂度，将时间复杂度降为O(n)，同时空间复杂度变为O(n)。

很多涉及到「两个变量」的题目，都可以枚举其中一个变量，把它当成常量看待，从而转化成「一个变量」的问题。通常来说「枚举右，寻找左」是更加好写的。

相似题目

题单第0.0.1节

和相等的子数组

子序列是一个数组中一段连续非空的元素组成的序列。

def findSubarrays(self, nums: List[int]) -> bool:
    hstable=dict()
    seen = set()
    for i in range(len(nums)-1):
        current_sum = nums[i]+nums[i+1]
        if current_sum in seen:
            return True
        seen.add(current_sum)
    return False

一开始以为子序列可以跳着选，我想的是用两个for循环遍历数组，算出所有的的和，记录和的序号，并做比较。

G 老师建议我使用 set（集合），因为题目只要求有没有。如果需要知道索引，还是得用 dict，应该类似上面哈希表的思路。