位运算与前缀和 · Bit / Prefix Sum

一句话骨架：① 位运算抓两个本质——异或「消除成对元素」、x & (x-1) 「消掉最低位 1」；② 前缀和把「区间和 = 前缀差」配合哈希表实现 O(n)「子数组和等于 K」。

两类必背骨架

# 1. 前缀和 + 哈希：subarray sum = k
prefix = 0; cnt = {0: 1}; ans = 0
for x in nums:
    prefix += x
    ans += cnt.get(prefix - k, 0)   # 之前出现过几次 prefix-k，就有几个子数组
    cnt[prefix] = cnt.get(prefix, 0) + 1

# 2. XOR 消同类
ans = 0
for x in nums: ans ^= x
return ans   # 出现两次的全消掉，剩下出现一次的

# 3. 前缀积 + 后缀积（不允许除法时的产品代替方案）
n = len(nums); ans = [1]*n; left = 1
for i in range(n): ans[i] = left; left *= nums[i]
right = 1
for i in range(n-1, -1, -1): ans[i] *= right; right *= nums[i]

关卡 1 · 只出现一次的数字

学习目标

背下 XOR 三性质（a^a=0, a^0=a, 交换律）；理解题目硬约束 O(n) 时间 + O(1) 空间是怎么逼出 XOR 的。

#136只出现一次的数字简单

♥♥♥♥♥+0 XP🔥 0

0 / 11

📝 题目

给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1

输入nums = [2,2,1]

输出1

示例 2

输入nums = [4,1,2,1,2]

输出4

示例 3

输入nums = [1]

输出1

约束

• 1 ≤ nums.length ≤ 3 × 10⁴
• -3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
• 除了某个元素只出现一次以外，数组中每个元素都恰好出现两次

💡 思路：XOR 三个性质：① `a ^ a = 0`；② `a ^ 0 = a`；③ 满足交换律和结合律。把所有元素 XOR 起来，相同的两两抵消，剩下的就是只出现一次的那个。O(n) 时间、O(1) 空间，比哈希表更优雅。

✅ 完整解法

时间 O(n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def singleNumber(nums: list[int]) -> int: 2    ans = 0 3    for x in nums: 4        ans ^= x      # 出现两次的会互相抵消（a ^ a = 0），剩下的就是只出现一次的 5    return ans

🐞 单步可视化

示例：nums = [4, 1, 2, 1, 2]

代码L2

 1def singleNumber(nums: list[int]) -> int: 2    ans = 0 3    for x in nums: 4        ans ^= x      # 出现两次的会互相抵消（a ^ a = 0），剩下的就是只出现一次的 5    return ans

数据流

ans0ans(bin)0000

nums

0

4

1

1

2

2

3

1

4

2

已 XOR 进 ans 的元素出现次数

空

1 / 17初始化 ans = 0（XOR 的单位元）

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

题目要求「线性时间 + 常量空间」直接排除了哪个朴素解？

a ^ a 的结果是？

a ^ 0 的结果是？

XOR 是否满足交换律 a ^ b = b ^ a 和结合律 (a ^ b) ^ c = a ^ (b ^ c)？

ans = 0 起步是否必须？

 1def singleNumber(nums: list[int]) -> int: 2    ans = 0 3    for x in nums: 4        ans ^= x      # 出现两次的会互相抵消（a ^ a = 0），剩下的就是只出现一次的 5    return ans

ans ^= x 是哪种操作的简写？

 1def singleNumber(nums: list[int]) -> int: 2    ans = 0 3    for x in nums: 4        ans ^= x      # 出现两次的会互相抵消（a ^ a = 0），剩下的就是只出现一次的 5    return ans

functools.reduce(operator.xor, nums) 与本题循环版的关系？

若题目改为「除某元素出现一次外、其余出现 3 次」（LC137），XOR 还能直接用吗？

若数组改为「两个数只出现一次，其余出现两次」（LC260），思路？

本题对负数也有效吗？

空间复杂度是？

关卡 2 · 和为 K 的子数组

学习目标

掌握「前缀和 + 哈希」模板；记住 cnt = {0: 1} 处理整段和等于 k 的边界。

#560和为 K 的子数组中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。

子数组是数组中元素的连续非空序列。

示例 1

输入nums = [1,1,1], k = 2

输出2

💡 [1,1] 出现两次（位置 0-1 和 1-2）

示例 2

输入nums = [1,2,3], k = 3

输出2

💡 [1,2] 与 [3]

示例 3

输入nums = [1,-1,0], k = 0

输出3

💡 [1,-1]、[-1,0...]、[0]

约束

• 1 ≤ nums.length ≤ 2 × 10⁴
• -1000 ≤ nums[i] ≤ 1000
• -10⁷ ≤ k ≤ 10⁷

💡 思路：前缀和 + 哈希表的招牌组合。子数组 `(i,j]` 的和 = `prefix[j] - prefix[i]`；要找「和为 k」就找「prefix[j] - prefix[i] = k」即 prefix[i] = prefix[j] - k。一边累计 prefix、一边查哈希表中 `prefix - k` 出现过几次（直接累加进答案），再把当前 prefix 写入哈希表。`cnt = {0: 1}` 是处理「从 nums[0] 开始整段和正好等于 k」的边界初始化。

✅ 完整解法

时间 O(n) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def subarraySum(nums: list[int], k: int) -> int: 2    cnt = {0: 1}        # 前缀和 0 「出现过 1 次」——处理「整段和恰好 = k」的边界 3    prefix = 0 4    ans = 0 5    for x in nums: 6        prefix += x 7        ans += cnt.get(prefix - k, 0)   # 之前出现过几次 prefix - k，就有几个以当前结尾的子数组和为 k 8        cnt[prefix] = cnt.get(prefix, 0) + 1 9    return ans

🐞 单步可视化

示例：nums = [1, 1, 1], k = 2

代码L2

 1def subarraySum(nums: list[int], k: int) -> int: 2    cnt = {0: 1}        # 前缀和 0 「出现过 1 次」——处理「整段和恰好 = k」的边界 3    prefix = 0 4    ans = 0 5    for x in nums: 6        prefix += x 7        ans += cnt.get(prefix - k, 0)   # 之前出现过几次 prefix - k，就有几个以当前结尾的子数组和为 k 8        cnt[prefix] = cnt.get(prefix, 0) + 1 9    return ans

数据流

k2prefix0ans0

nums

0

1

1

1

2

1

cnt（前缀和 → 出现次数）

0→1

1 / 14初始化 cnt = {0: 1}（处理整段和=k 的边界）

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

本题为什么用前缀和而不是滑动窗口？

子数组 (i, j] 的和等于 prefix[j] - prefix[i]——这里 (i, j] 是闭还是开？

哈希表里 key 与 value 的语义是？

 1def subarraySum(nums: list[int], k: int) -> int: 2    cnt = {0: 1}        # 前缀和 0 「出现过 1 次」——处理「整段和恰好 = k」的边界 3    prefix = 0 4    ans = 0 5    for x in nums: 6        prefix += x 7        ans += cnt.get(prefix - k, 0)   # 之前出现过几次 prefix - k，就有几个以当前结尾的子数组和为 k 8        cnt[prefix] = cnt.get(prefix, 0) + 1 9    return ans

cnt = {0: 1} 这个初始化的关键作用是？

 1def subarraySum(nums: list[int], k: int) -> int: 2    cnt = {0: 1}        # 前缀和 0 「出现过 1 次」——处理「整段和恰好 = k」的边界 3    prefix = 0 4    ans = 0 5    for x in nums: 6        prefix += x 7        ans += cnt.get(prefix - k, 0)   # 之前出现过几次 prefix - k，就有几个以当前结尾的子数组和为 k 8        cnt[prefix] = cnt.get(prefix, 0) + 1 9    return ans

ans += cnt.get(prefix - k, 0) 与 cnt[prefix] = cnt.get(prefix, 0) + 1，哪个先做？

 1def subarraySum(nums: list[int], k: int) -> int: 2    cnt = {0: 1}        # 前缀和 0 「出现过 1 次」——处理「整段和恰好 = k」的边界 3    prefix = 0 4    ans = 0 5    for x in nums: 6        prefix += x 7        ans += cnt.get(prefix - k, 0)   # 之前出现过几次 prefix - k，就有几个以当前结尾的子数组和为 k 8        cnt[prefix] = cnt.get(prefix, 0) + 1 9    return ans

cnt.get(prefix - k, 0) 这个 0 默认值的意义？

 1def subarraySum(nums: list[int], k: int) -> int: 2    cnt = {0: 1}        # 前缀和 0 「出现过 1 次」——处理「整段和恰好 = k」的边界 3    prefix = 0 4    ans = 0 5    for x in nums: 6        prefix += x 7        ans += cnt.get(prefix - k, 0)   # 之前出现过几次 prefix - k，就有几个以当前结尾的子数组和为 k 8        cnt[prefix] = cnt.get(prefix, 0) + 1 9    return ans

为什么暴力 O(n²) 超时但本题 O(n) 能过？

本题与 two-sum 在思维上的最大共性是？

若 nums 全为非负数，能否改用滑动窗口？

空间复杂度?

若题目改为「找最长和为 k 的子数组」（LC325），需要怎么改？

prefix += x; ans += ...; cnt[prefix] = ... 这三步顺序写错的常见 bug？

关卡 3 · 除自身以外数组的乘积

学习目标

理解「不能用除法」的现实约束；用「前缀积 + 后缀积」两遍扫描共用一份 answer 实现 O(1) 额外空间。

#238除自身以外数组的乘积中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1

输入nums = [1,2,3,4]

输出[24,12,8,6]

示例 2

输入nums = [-1,1,0,-3,3]

输出[0,0,9,0,0]

💡 含 0 时尤其能体现「不能用除法」的必要性

约束

• 2 ≤ nums.length ≤ 10⁵
• -30 ≤ nums[i] ≤ 30
• 所有前缀积、后缀积都在 32 位整数范围内

💡 思路：`answer[i] = (左侧乘积) * (右侧乘积)`。两遍扫描：第一遍从左到右把「i 左侧所有元素的乘积」存到 `answer[i]`；第二遍从右到左用一个滚动变量 right 把「i 右侧所有元素的乘积」乘进去。共用 answer 数组让额外空间降到 O(1)（不计输出）。

✅ 完整解法

时间 O(n) · 空间 O(1) 不计输出 answer 数组

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

🐞 单步可视化

示例：nums = [1, 2, 3, 4]

代码L1

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

数据流

left1right1

nums

0

1

1

2

2

3

3

4

answer

0

1

1

1

2

1

3

1

result[1,1,1,1]

1 / 30函数入口：productExceptSelf(nums)，nums = [1, 2, 3, 4]

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

题目明确禁止「除法」，最大原因是？

answer[i] 的核心分解是？

第一遍循环结束后，answer[i] 的语义是？

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

answer[i] = left; left *= nums[i] 这两行的顺序为何不能调换？

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

第二遍从右到左写入时，为什么用 *= 而不是 =？

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

right 这个滚动变量在第二遍循环中的语义是？

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

for i in range(n - 1, -1, -1) 这是从哪里到哪里的循环？

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

O(1) 额外空间的关键是什么？

answer = [1]*n 这个初始值有什么用？

 1def productExceptSelf(nums: list[int]) -> list[int]: 2    n = len(nums) 3    answer = [1] * n 4  5    # 第一遍：answer[i] = 「i 左侧所有元素的乘积」 6    left = 1 7    for i in range(n): 8        answer[i] = left 9        left *= nums[i]10 11    # 第二遍：从右往左，把「i 右侧所有元素的乘积」乘进去12    right = 113    for i in range(n - 1, -1, -1):14        answer[i] *= right15        right *= nums[i]16 17    return answer

示例 nums=[1,2,3,4]：第一遍跑完 answer 是？

若题目允许除法、且无 0，最朴素的解是？

本题最常见的扩展场景？

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
169	多数元素	简单	Boyer-Moore 摩尔投票：候选 + 计数对消（与 XOR「成对消除」同源思想）
75	颜色分类	中等	三指针（low / mid / high）一次扫——前缀和的「三段划分」变体
287	寻找重复数	中等	视为「下标 → 值」的隐式链表，Floyd 判环找重复元素
31	下一个排列	中等	从右往左找第一个降点 + 右段反转——和前/后缀扫的双向思想类似

面试常踩

• XOR 起步用 0：0 是 XOR 的单位元（a^0=a），从其它值起步会污染答案。
• cnt = {0: 1} 的初始化不能省——否则「整段和恰好 = k」漏解。
• prefix += x; ans += ...; cnt[prefix] = ...：先查后存的纪律和 two-sum 一脉相承。k=0 时尤其暴露这种 bug。
• 238 不能用除法——nums 含 0 时除零不可避免；必须用前缀积/后缀积两遍扫描。
• 238 O(1) 空间：第一遍把左积写进 answer、第二遍滚动变量 right 乘进去。这是「输出不算额外空间」的经典空间优化。