数组与哈希 解题模板

适用场景

• 数组遍历：需要线性扫描、区间操作、原地修改

• 哈希表：O(1) 查找是否存在、计数、去重

• 双指针：有序数组的查找/去重/分区

通用模板

哈希表（查补数 / 计数）

 
# 查补数（两数之和）
 
seen = {}
 
for i, num in enumerate(nums):
 
    if target - num in seen:
 
        return [seen[target - num], i]
 
    seen[num] = i
 
# 计数（字母异位词）
 
counter = {}
 
for c in s:
 
    counter[c] = counter.get(c, 0) + 1
 

双指针（有序数组 / 区间）

 
# 相向双指针
 
l, r = 0, len(nums) - 1
 
while l < r:
 
    if condition(l, r): l += 1
 
    else: r -= 1
 
# 同向快慢指针
 
slow = 0
 
for fast in range(len(nums)):
 
    if nums[fast] != target:  # 根据条件调整
 
        nums[slow] = nums[fast]
 
        slow += 1
 

前缀和

 
prefix = [0]
 
for num in nums:
 
    prefix.append(prefix[-1] + num)
 
# 子数组 [l, r] 和 = prefix[r+1] - prefix[l]
 

复杂度总结

模式	时间	空间	典型题
哈希表一次遍历	O(n)	O(n)	两数之和、最长连续序列
双指针夹逼	O(n)	O(1)	三数之和、接雨水、盛水容器
快慢指针	O(n)	O(1)	删除重复项、移动零
前缀和	O(n)	O(n)	和为K子数组、连续数组

常见变体

• 两数之和 → 三数之和 → 四数之和（固定 + 双指针）

• 存在重复 I → II（距离限制）

• 前缀和 + 哈希表 → 任意子数组 O(1) 求和

关键要点

• 哈希表存值还是存下标？

• 双指针移动条件 + 边界检查

• 原地修改时注意元素覆盖顺序

• 前缀和的差值是子数组和（不是前缀和本身）

→ 查看该分类题目：LeetCode学习路线图 > 一、数组与哈希

---

相似题对比

易混题对	关键区别	相同点
1两数之和 vs 167两数之和II	无序 vs 有序	查补数
15三数之和 vs 18四数之和	固定1个+双指针 vs 固定2个+双指针	排序+去重+双指针
53最大子数组和 vs 152乘积最大子数组	加法简单(max) vs 乘法需同时跟踪min	Kadane思想
525连续数组 vs 560和为K的子数组	求最长 vs 求个数	前缀和+哈希表

---

测试用例模板

 
# 基础功能
 
assert func([2,7,11,15], 9) == [0,1]  # 普通情况
 
assert func([3,3], 6) == [0,1]          # 两个相同元素
 
assert func([1], 1) == [0]              # 单元素
 
# 边界
 
assert func([], 0) == None              # 空数组
 
assert func([1,2], 4) == None           # 无解
 

---

关联题型

关联题型	常见结合方式	典型题目
二分查找	有序数组 + 二分查找优化	33搜索旋转排序数组, 34搜索范围
滑动窗口	连续子数组 + 窗口维护	209长度最小的子数组
排序	数组排序 + 自定义比较器	56合并区间