1.two-sum.py

#
# @lc app=leetcode id=1 lang=python3
#
# [1] Two Sum
#
# Difficulty: Easy
# Frequency: 100.0%
# Tags: Array, Hash Table
# URL: https://leetcode.com/problems/two-sum/
#
# --- Problem Description ---
#
# Given an array of integers nums and an integer target, return indices of the
# two numbers such that they add up to target.
#
# You may assume that each input would have exactly one solution, and you may
# not use the same element twice.
#
# You can return the answer in any order.
#
#
#
# Example 1:
#
# Input: nums = [2,7,11,15], target = 9
# Output: [0,1]
# Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
#
# Example 2:
#
# Input: nums = [3,2,4], target = 6
# Output: [1,2]
#
# Example 3:
#
# Input: nums = [3,3], target = 6
# Output: [0,1]
#
#
#
# Constraints:
#
# 	  - 2 <= nums.length <= 10^(4)
# 	  - -10^(9) <= nums[i] <= 10^(9)
# 	  - -10^(9) <= target <= 10^(9)
# 	  - Only one valid answer exists.
#
#
#
# Follow-up: Can you come up with an algorithm that is less than O(n^(2)) time
# complexity?
#

#
# --- Community Solutions ---
#
# https://leetcode.com/problems/two-sum/solutions
#

# Hash Table / Complement Lookup - O(n) time, O(n) space
#
# 清单定位：
#   常用数据结构 / 哈希与集合，rank #1。
#   这题是哈希表最核心的模板：一边扫描，一边把"之前见过的信息"存起来。
#
# 这题其实在做什么：
#   对每个数 nums[i] = x，问一句：前面有没有某个数 y，让 x + y == target？
#   也就是前面有没有 target - x。
#
# 识别信号：
#   - "two numbers add up to target" -> 配对 / 补数
#   - 要返回下标，而不是只判断存在 -> hash map 里要存 index
#   - follow-up 要小于 O(n^2) -> 不能双重循环，应该用哈希表 O(1) 查询
#
# 为什么暴力不行：
#   双重循环枚举每一对下标是 O(n^2)。n 到 10^4 时还能勉强，但这题的目的
#   是训练：把"查找另一个数"从线性扫描变成 hash map 查询。
#
# 核心思路：
#   单趟扫描。扫到当前数 x 时，先查 target - x 是否已经在表里。
#   - 如果在，说明前面的那个数和当前数正好配成答案，直接返回两个下标。
#   - 如果不在，把 x 和它的下标存起来，留给后面的数来配对。
#
#   这份代码存的是"已见数字 -> 下标"；另一种等价写法是存"需要的补数 -> 下标"。
#   两者的主干一样：当前数字只和左边已经扫过的数字配对。
#
# 跑例：nums = [3, 2, 4], target = 6
#
#   i=0, x=3, need=3, 表里没有 3 -> 存 3:0
#   i=1, x=2, need=4, 表里没有 4 -> 存 2:1
#   i=2, x=4, need=2, 表里有 2:1 -> 返回 [2, 1]
#
# 关键状态 / 不变量：
#   com = 已经扫描过的数字 -> 它的下标。
#   不变量：进入第 i 轮时，com 只包含下标 < i 的元素。
#   所以一旦命中 target - nums[i]，两个下标天然不同，不会重复使用同一个元素。
#
# 边界条件 / 易错例：
#   - nums = [3, 3], target = 6：第一轮存 3:0，第二轮当前 3 命中前一个 3。
#   - 不能先存当前数再查，否则 target = 6, x = 3 时可能错误地用同一个下标配自己。
#   - 有负数也没区别，补数 target - x 仍然可以作为 hash key。
#
# 落码步骤 / 伪代码骨架：
#   1. 建空字典 com。
#   2. 从左到右枚举 i, x。
#   3. need = target - x；如果 need 在 com 中，返回 [i, com[need]]。
#   4. 否则记录 com[x] = i。
#
# 复杂度：
#   - 时间 O(n)：每个数只扫描一次，字典查询和写入平均 O(1)。
#   - 空间 O(n)：最坏情况下答案在最后，字典里会存接近 n 个数。
#
# 一句模板：
#   两数配 target -> 扫当前 x，查左边是否见过 target - x。
#
# 记忆锚点：
#   "先查再存"保证不复用当前下标；hash map 负责把找搭档从 O(n) 变成 O(1)。
#
# 主动回忆检查：
#   - com 里为什么只能放"左边已经扫描过"的数字？
#   - 如果题目只问是否存在一对数字，hash map 里还需要存 index 吗？

# @lc code=start
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # com 只记录当前下标左边的数字：value -> index。
        # 命中补数时，两个下标天然不同。
        com = {}
        for i, seen in enumerate(nums):
            if target - seen in com:
                return [i, com[target - seen]]

            # 当前数还没有找到搭档，就留给后面的数字来配对。
            com[seen] = i
                
# @lc code=end