数组与字符串

一句话：数组题的大部分”技巧”其实只有两类——用下标/原地交换省掉额外空间，或者用一次预处理把重复计算的区间查询/更新降到 O(1)。认出属于哪一类，思路就定了一半。

原地操作：不额外开空间

一批题看起来毫无关系（删除重复项、旋转矩阵、螺旋遍历、缺失的第一个正数），但都在回答同一个问题：能不能不用额外数组，只靠交换/覆盖/多个下标配合，把结果原地写出来？

核心武器是双下标分工：一个下标扫描（读指针），一个下标标记”已确定区域的边界”（写指针），扫描时只在满足条件时才推进写指针。26-删除有序数组中的重复项、27-移除元素、283-移动零都是这个模板的变体，区别只在”什么算满足条件”。

矩阵类（48-旋转图像、54-螺旋矩阵、73-矩阵置零）的原地技巧是另一路：用矩阵自身的第一行/第一列当标记位，或者找规律做多次局部转置代替额外矩阵——本质仍是”不开新空间，靠下标腾挪”。

41-缺失的第一个正数是这类题的巅峰：把数组当成哈希表用——下标 i 的位置应该放值 i+1，一次遍历把每个数交换到它该在的位置，最后从头扫一遍找到第一个不对的下标。O(1) 空间做到哈希表的效果，代价是要读写原数组。

前缀和与差分：预处理换查询复杂度

303/304-区域和检索、560-和为K的子数组、238-除自身以外数组的乘积 表面是不同题，实际都在问同一件事：“某个区间的聚合值”要被反复查询，能不能一次预处理，把每次查询降到 O(1)？

前缀和 prefix[i] = sum(nums[0..i-1])，区间和 sum(l, r) = prefix[r+1] - prefix[l]——下标错一位是最大的坑，务必固定 prefix[0] = 0 这个哨兵，否则左边界为 0 的区间要单独判断。238 是前缀和的双向版本：左边一次遍历、右边一次遍历，分别累乘再相乘，绕开”不能用除法”的限制。

差分数组是前缀和的逆运算，把”区间更新”降到 O(1)：diff[l] += v; diff[r+1] -= v，最后对 diff 做前缀和还原成结果数组。1094-拼车、1109-航班预订统计都是”多次区间加，问最终每个点的值”，这正是差分存在的理由——如果每次区间更新都真的遍历整个区间，退化成 O(n²)。

560-和为K的子数组 把前缀和更进一步：用哈希表记录”某个前缀和出现过几次”，把”求有多少子数组和为 K”变成”对每个右端点，查有多少个左端点满足 prefix[r] - prefix[l] = K”——前缀和从”降复杂度的预处理”升级成”配合哈希表做计数”。

易错点：原地操作的顺序依赖

原地技巧最容易犯的错是读指针已经跨过写指针要写的位置（提前覆盖了还没读到的数据）——旋转数组、原地反转类问题尤其容易中招。判断方法：想清楚”写指针永远追不上读指针”这个不变量在你的实现里是否成立，而不是跑一个用例侥幸通过。