01 数组 / 双指针 / 滑动窗口

最基础，必须无脑AC

🔖 #1 · Two Sum ★

难度: Medium | 标签: Array, HashMap | 链接: https://leetcode.com/problems/two-sum/

题目描述

给定整数数组 nums 和目标值 target，返回和为 target 的两个数组下标。

解题思路

用 HashMap 存储 已经遇到的数 → 下标。遍历时判断 target - nums[i] 是否已在 map 中。
  • 时间复杂度 O(n)
  • 空间复杂度 O(n)

答案代码

def twoSum(nums, target):
    seen = {}
    for i, v in enumerate(nums):
        if target - v in seen:
            return [seen[target - v], i]
        seen[v] = i

扩展总结

  • 变体：3Sum (#15)、4Sum (#18) — 排序+双指针峰为模板
  • HashMap 方式只适用于 unordered，3Sum 要去重需要排序
  • QR 面试中常考 follow-up：如果输入有重复怎么办？如果要所有对怎么办？

🔖 #15 · 3Sum ★

难度: Medium | 标签: Array, Two Pointer | 链接: https://leetcode.com/problems/3sum/

题目描述

找出数组中所有和为 0 的三元组（不重复）。

解题思路

  1. 先排序数组
  1. 固定第一个数 nums[i]，然后双指针向中间找
  1. 去重：跳过相同的 nums[i] 和左右指针相同的元素

答案代码

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
            elif s < 0:
                l += 1
            else:
                r -= 1
    return res

扩展总结

  • 双指针必须先排序，O(n²) 是最优
  • 去重逻辑是易错点，面试必考
  • 4Sum 类似，外层再套一层就可以

🔖 #42 · Trapping Rain Water ★

难度: Hard | 标签: Array, Two Pointer, Stack | 链接: https://leetcode.com/problems/trapping-rain-water/

题目描述

给定表示地形高度的数组，计算据此可以接多少雨水。

解题思路

双指针法（推荐）：维护 leftMax 和 rightMax。哪边小，哪边移动。
  • 每个位置蓄水量 = min(leftMax, rightMax) - height[i]

答案代码

def trap(height):
    l, r = 0, len(height) - 1
    lmax = rmax = res = 0
    while l < r:
        if height[l] <= height[r]:
            if height[l] >= lmax:
                lmax = height[l]
            else:
                res += lmax - height[l]
            l += 1
        else:
            if height[r] >= rmax:
                rmax = height[r]
            else:
                res += rmax - height[r]
            r -= 1
    return res

扩展总结

  • 另一种方法：单调栈 O(n) 时间 O(n) 空间
  • 前后缀数组法：预计算 leftMax/rightMax 数组
  • #84 Largest Rectangle in Histogram 是相关题，单调栈模型

🔖 #53 · Maximum Subarray ★

难度: Medium | 标签: DP, Array | 链接: https://leetcode.com/problems/maximum-subarray/

题目描述

找具有最大和的连续子数组。

解题思路

Kadane 算法：dp[i] = 以 nums[i] 结尾的最大子数组。转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])

答案代码

def maxSubArray(nums):
    cur = res = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)
        res = max(res, cur)
    return res

扩展总结

  • 变体：#152 Maximum Product Subarray — 同时维护最大/最小值
  • 返回子数组的左右界时需要额外记录
  • 面试高频：如果要圈形数组怎么办？（总和 - 最小子数组）

🔖 #121 · Best Time to Buy and Sell Stock ★

难度: Easy | 标签: Array, DP | 链接: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

题目描述

给定股票每日价格，最多进行一笔交易，求最大利润。

解题思路

维护一个左侧最小值，设当前差为 prices[i] - minSoFar。

答案代码

def maxProfit(prices):
    min_p = float('inf')
    res = 0
    for p in prices:
        min_p = min(min_p, p)
        res = max(res, p - min_p)
    return res

扩展总结

  • QR必考，还要掌握 #123（最多2笔）和 #188（最多k笔）
  • 状态机 DP 是 #123/#188 的核心，定义 hold/unhold 状态
  • #122 无限次交易可贪心解决

🔖 #560 · Subarray Sum Equals K ★

难度: Medium | 标签: Array, Prefix Sum, HashMap | 链接: https://leetcode.com/problems/subarray-sum-equals-k/

题目描述

找和等于 k 的连续子数组的个数。

解题思路

前缀和 + HashMap：prefix[j] - prefix[i] = k => 查找 prefix[j] - k 有多少个。

答案代码

from collections import defaultdict
def subarraySum(nums, k):
    count = defaultdict(int)
    count[0] = 1
    prefix = res = 0
    for n in nums:
        prefix += n
        res += count[prefix - k]
        count[prefix] += 1
    return res

扩展总结

  • 前缀和是将 O(n²) 降低到 O(n) 的经典技巧
  • 注意：数组元素可以为负数，不能用滑窗
  • 相关：#523 连续子数组和为 k 的倍数

🔖 #76 · Minimum Window Substring

难度: Hard | 标签: Sliding Window, HashMap | 链接: https://leetcode.com/problems/minimum-window-substring/

题目描述

给定字符串 s 和 t，找 s 中包含 t 所有字符的最小子串。

解题思路

滑动窗口模板：用 need 和 window 两个计数器，formed 记录已满足的字符种类数。

答案代码

from collections import Counter
def minWindow(s, t):
    need = Counter(t)
    window = {}
    formed = 0
    required = len(need)
    l = 0
    res = ""
    for r, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            formed += 1
        while formed == required:
            if not res or r - l + 1 < len(res):
                res = s[l:r+1]
            window[s[l]] -= 1
            if s[l] in need and window[s[l]] < need[s[l]]:
                formed -= 1
            l += 1
    return res

扩展总结

  • 滑窗精高：先扩张再收缩，收缩条件是已满足要求
  • 相关：#438 Find All Anagrams、#567 Permutation in String