一维数组
2026/4/10大约 23 分钟常用算法题一维数组
本章题海战术
一维数组介绍
面试官：好的，我们来聊聊一维数组相关的算法题。你能先梳理一下一维数组最常考的核心题型和对应的解题套路吗？
候选人：没问题。一维数组是算法面试的基础中的基础，核心考察数组下标、指针、哈希表、前缀和、差分这些基础工具的灵活运用。我把常考题型归纳为 5 大类，每个类型都有固定的解题模板，掌握了就能覆盖 90% 以上的大厂面试题 🚀
核心题型与解题套路总览
| 解题方法 | 适用场景 | 时间复杂度 | 空间复杂度 | 典型例题 |
|---|---|---|---|---|
| 双指针法 | 元素删除、数对查找、数组划分 | O(n) | O(1) | 移除元素(leetcode 27)、三数之和(leetcode 15)、合并有序数组(leetcode 88) |
| 前缀和 / 差分 | 区间和查询、区间批量更新 | 预处理 O (n)，查询 O (1) | O(n) | 区域和检索(leetcode 303)、航班预订统计(leetcode 1109) |
| 哈希表辅助 | 元素查找、下标匹配、去重 | O(n) | O(n) | 两数之和(leetcode 1)、最长连续序列(leetcode 128) |
| 二分查找 | 有序数组的查找、定位 | O(logn) | O(1) | 搜索插入位置(leetcode 35)、旋转数组找最小值(leetcode 153) |
| 原地修改 | 要求空间复杂度 O (1) | O(n) | O(1) | 旋转数组(leetcode 33)、缺失的第一个正数(leetcode 41) |
高频题型详解（附 Java 代码）
1. 双指针法（最常考，占比 60%+）
核心思路：用两个指针同向 / 相向遍历数组，将暴力解法的 O (n²) 时间复杂度直接降到 O (n)，且通常支持原地修改。
执行流程图（以 "移除元素" 为例(leetcode 27)）：
典型例题：移除元素(leetcode 27)
// 题目：移除数组中所有等于val的元素，返回新数组长度（原地修改）
public int removeElement(int[] nums, int val) {
int slow = 0; // 慢指针：指向新数组的下一个插入位置
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}关键点：快慢指针的分工明确，无需额外空间 ✅
2. 前缀和与差分法
核心思路：预处理数组生成前缀和 / 差分数组，将区间操作从 O (n) 降到 O (1)，适合频繁查询的场景。
典型例题：区域和检索 - 数组不可变(leetcode 303)
class NumArray {
private int[] prefixSum; // 前缀和数组，prefixSum[i]表示前i个元素的和
public NumArray(int[] nums) {
prefixSum = new int[nums.length + 1]; // 下标从1开始，避免边界判断
for (int i = 0; i < nums.length; i++) {
prefixSum[i+1] = prefixSum[i] + nums[i];
}
}
// 查询[left, right]区间的和
public int sumRange(int left, int right) {
return prefixSum[right+1] - prefixSum[left];
}
}关键点：前缀和数组下标偏移 1，处理 left=0 的边界情况 🔑
3. 哈希表辅助法
核心思路：用哈希表存储已遍历元素及其下标，将查找时间从 O (n) 降到 O (1)，适合 "查找匹配元素" 的场景。
典型例题：两数之和(leetcode 1)
// 题目：在数组中找出两个数之和等于target，返回它们的下标
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i); // 存储当前元素和下标
}
return new int[]{-1, -1}; // 题目保证有解，此处为兜底
}关键点：边遍历边存哈希表，只需一次遍历 ⚡
4. 二分查找法（有序数组专属）
核心思路：利用数组的有序性，每次排除一半元素，时间复杂度 O (logn)，是有序数组查找的最优解。
典型例题：搜索插入位置(leetcode 35)
// 题目：在有序数组中查找target，找到返回下标，找不到返回应插入的位置
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) { // 注意边界：闭区间用<=
int mid = left + (right - left) / 2; // 防止int溢出，不用(left+right)/2
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left; // 循环结束时left=right+1，即为插入位置
}关键点：边界条件判断（闭区间 vs 开区间）、防止溢出 💡
面试加分项 ✨
- 主动分析复杂度：写完代码后立刻说出时间和空间复杂度，并说明是否有优化空间
- 边界覆盖：主动提及空数组、单元素数组、重复元素等边界情况
- 解法对比：能对比暴力解法和最优解法的优劣，说明为什么选择当前解法
- 举一反三：能说出同类型的其他题目（比如双指针法还能解决 "盛最多水的容器"）
- 代码规范：变量名有意义，代码简洁，无冗余逻辑
避坑指南 ❌
- 不要上来就写暴力解法，先想最优解法，实在想不出来再写暴力解法并说明优化方向
- 二分查找时注意边界条件，闭区间用
left <= right，开区间用left < right - 前缀和数组注意下标偏移，通常从 1 开始更方便
- 哈希表注意 key 重复的问题，比如两数之和中不能使用同一个元素两次
- 原地修改时注意不要覆盖还未使用的元素
面试官：
很好，那你能手写一下三数之和(leetcode 15)的最优解法吗？
候选人：
没问题。三数之和(leetcode 15)的最优解法是先排序，然后固定一个数，用双指针找另外两个数，时间复杂度 O (n²)，空间复杂度 O (logn)（排序的空间）。需要特别注意去重逻辑，避免重复的三元组。
核心技术亮点代码（大厂高频必考题）
1. 三数之和（排序 + 双指针 + 三重去重）(leetcode 15)
技术亮点：将暴力 O (n³) 降到 O (n²)，原地去重避免重复三元组，是双指针法的集大成者
// 题目：找出数组中所有和为0的不重复三元组
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) return res;
Arrays.sort(nums); // 排序：双指针的前提 O(nlogn)
for (int i = 0; i < nums.length - 2; i++) {
// 亮点1：第一个数大于0，直接终止（排序后后面更大，和不可能为0）
if (nums[i] > 0) break;
// 亮点2：对第一个数去重，避免重复三元组
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 亮点3：对左右指针分别去重
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
// 去重后同时移动指针
left++;
right--;
} else if (sum < 0) {
left++; // 和太小，左指针右移
} else {
right--; // 和太大，右指针左移
}
}
}
return res;
}核心加分点：主动说明排序的空间复杂度是 O (logn)（Java 快排的递归栈空间），是该题的最优解 🔥
2. 最长连续序列（哈希表 O (n) 时间优化）(leetcode 128)
技术亮点：打破 "排序找连续序列" 的思维定式，用哈希表实现 O (n) 时间复杂度
// 题目：找出数组中最长连续序列的长度，要求时间复杂度O(n)
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
int maxLen = 0;
for (int num : set) {
// 亮点：只从连续序列的起点开始计算（如果num-1存在，说明num不是起点）
if (!set.contains(num - 1)) {
int currentNum = num;
int currentLen = 1;
while (set.contains(currentNum + 1)) {
currentNum++;
currentLen++;
}
maxLen = Math.max(maxLen, currentLen);
}
}
return maxLen;
}核心加分点：主动证明时间复杂度是 O (n)—— 每个元素最多被访问两次（加入集合 + 遍历一次）⚡
3. 缺失的第一个正数（原地哈希 O (1) 空间）(leetcode 41)
技术亮点：利用数组本身作为哈希表，实现 O (1) 额外空间，是原地修改的天花板题目
// 题目：找出未排序数组中缺失的最小正整数，要求O(n)时间O(1)空间
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 核心思路：将数字i放到下标i-1的位置（1→0, 2→1, ..., n→n-1）
for (int i = 0; i < n; i++) {
// 亮点：循环交换直到当前位置的数字正确，或数字不在[1,n]范围内
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// 交换nums[i]和nums[nums[i]-1]
int temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
// 遍历数组，第一个下标i与值不匹配的位置，i+1就是答案
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 所有位置都正确，缺失的是n+1
return n + 1;
}核心加分点：主动说明为什么只处理 [1,n] 范围内的数字 —— 因为长度为 n 的数组，缺失的最小正整数一定在 [1,n+1] 之间 🔑
4. 旋转数组（三次反转法 O (1) 空间）(leetcode 33)
技术亮点：用三次原地反转实现数组旋转，替代额外数组的 O (n) 空间解法
// 题目：将数组向右旋转k步，要求O(1)额外空间
public void rotate(int[] nums, int k) {
k %= nums.length; // 处理k大于数组长度的情况
// 三次反转法
reverse(nums, 0, nums.length - 1); // 反转整个数组
reverse(nums, 0, k - 1); // 反转前k个元素
reverse(nums, k, nums.length - 1); // 反转后n-k个元素
}
// 反转数组[start, end]区间
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}核心加分点：主动画图说明三次反转的过程，直观展示为什么能得到正确结果 ✨
一维数组算法题核心技术难点与解决方案
| 技术难点 | 问题表现 | 通用解决方案 | 典型例题 |
|---|---|---|---|
| 边界条件处理 | 空数组、单元素数组、数组全是目标值、下标越界 | 1. 开头先判空 2. 循环条件严格对应区间类型 3. 测试极端用例（空、单元素、全相同） | 二分查找(leetcode 704)、移除元素(leetcode 27) |
| 重复元素去重 | 结果中出现重复项、去重不彻底导致超时 | 1. 排序后相邻元素比较去重 2. 哈希表存储已出现元素 3. 指针移动时跳过重复值 | 三数之和(leetcode 15)、四数之和(leetcode 18) |
| O (1) 空间复杂度要求 | 不允许使用额外数组 / 哈希表 | 1. 原地修改（双指针覆盖） 2. 原地哈希（用数组下标映射值） 3. 原地反转 | 旋转数组(leetcode 33)、缺失的第一个正数(leetcode 41) |
| 区间操作效率低 | 频繁查询 / 更新区间导致 O (n) 超时 | 1. 前缀和：区间和查询 O (1) 2. 差分：区间批量更新 O (1) | 区域和检索(leetcode 303)、航班预订统计(leetcode 1109) |
| 有序性利用不足 | 对有序数组用暴力解法，时间复杂度高 | 1. 二分查找（O (logn)） 2. 双指针（相向 / 同向） 3. 利用有序性提前终止循环 | 搜索插入位置(leetcode 35)、合并有序数组(leetcode 88) |
| 哈希表冲突与重复 | 两数之和使用同一个元素、重复 key 覆盖 | 1. 边遍历边存哈希表（避免重复使用） 2. 存储元素最后一次出现的下标 3. 用 Set 去重后再处理 | 两数之和(leetcode 1)、最长连续序列(leetcode 128) |
面试终极加分项 🏆
写完代码后主动说：" 以上是我对一维数组核心题型的理解。我在刷题时总结了一个经验：一维数组的所有算法题，本质上都是在用空间换时间或者用时间换空间。比如哈希表是空间换时间，原地修改是时间换空间。面试官您可以随便抽一道一维数组的题，我都能快速给出最优解法。"
真实面试模拟
真实面试模拟
面试官（微笑着合上简历）：
“前面JVM和集合都聊得不错，基本功很扎实。那咱们换个方向，考察一下一维数组的算法题。这可以说是大厂面试的‘必点菜’，你先别紧张，随便聊聊：你平时刷这类题，心里有没有个大概的分类框架？🤔”
我：
有的面试官。我把一维数组的高频套路分成了六大类，拿到题目先往这六个模子里套，再根据限制条件微调。我给您画个脑图就清楚了：
面试官（点头）：
“分得挺细。那先说说第一类——遍历+统计，你提到最大子数组和(leetcode 53)、摩尔投票(leetcode 169)，这两个题核心思想分别是什么？”
我：
这两题的核心都是用 O(1) 空间维护遍历状态，不依赖额外数组。
- 最大子数组和（LeetCode 53）：动态规划的思想压缩成一个变量。
- 公式就一句话：
dp = Math.max(num, dp + num)意思是在每个位置，要么“另起炉灶”从当前元素开始，要么“加入前面的队伍”。 - 全程用
max记录最大值。
- 公式就一句话：
- 多数元素（LeetCode 169）摩尔投票：对拼消耗。
- 假设第一个是候选人，票数=1；往后遇到相同的票数+1，不同票数-1，票数归零就换候选人。
- 因为目标数字出现次数超过一半，它最后肯定能把其他数字全拼掉活下来 😎。
// 摩尔投票极简版
int cand = nums[0], count = 1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) { cand = nums[i]; count = 1; }
else if (nums[i] == cand) count++;
else count--;
}面试官：
“好，那第二类双指针，你能举个对撞指针的经典题，并说清楚为什么移动‘短板’一定不会漏掉最优解？”
我：
盛最多水的容器（LeetCode 11）。
左右指针 i=0, j=n-1，每次计算面积 min(height[i], height[j]) * (j-i)，然后移动较矮的那块板。
您看这个示意图就能秒懂👇：
高 ┃
↑ ┃ ┃
│ ┃ ┃ ┃
│ ┃ ┃ ┃ ┃
│ ┃ ┃ ┃ ┃
└─────────────────→ 索引
i → ← j
矮板 高板
移动矮板 i：宽度-1，但可能遇到更高的板 → 面积可能增大 ✅
移动高板 j：宽度-1，高度受限于矮板 i → 面积必然不变或减小 ❌数学上这叫“排除法”：因为面积由短板决定，移动长板只会让宽度减小，高度不可能增加，所以这一半的情况可以直接舍弃。复杂度 O(n)。
int i = 0, j = height.length - 1, max = 0;
while (i < j) {
max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
if (height[i] < height[j]) i++;
else j--;
}面试官：
“嗯，排除法的思想很清晰。那滑动窗口呢？比如‘无重复字符的最长子串(leetcode 3)’，窗口左边界跳转的细节你怎么处理？”
我：
这题关键是用哈希表记录字符最后一次出现的位置。
右指针 right 一路扩张，左指针 left 不能一步一步挪，必须直接跳到 max(left, 上次出现位置+1)，这样才能保证窗口内永远无重复。每步更新最大长度即可。
int[] index = new int[128]; // 初始化为-1
Arrays.fill(index, -1);
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
left = Math.max(left, index[c] + 1);
maxLen = Math.max(maxLen, right - left + 1);
index[c] = right;
}时间 O(n)，每个字符至多被左右指针访问一次。
面试官（推推眼镜）：
“接下来前缀和，给你一道题：和为K的子数组（LeetCode 560），暴力是 O(n²)，怎么优化到 O(n)？”
我：
核心转化：pre[i] - pre[j-1] = k → pre[j-1] = pre[i] - k。
遍历时，用一个 HashMap 存前缀和出现的次数，到位置 i 时查一下 pre-k 出现了几次，累加到答案里就行。
Map<Integer,Integer> map = new HashMap<>();
map.put(0, 1); // 前缀0出现1次
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}时间 O(n)，空间 O(n)，典型的空间换时间思路。
面试官：
“那二分查找如果放到‘旋转排序数组(leetcode 33)’里，怎么判断该搜左半段还是右半段？”
我：
核心是：mid 将数组分成两半，至少有一半是有序的。
我们先判断哪边有序，再看 target 是否落在有序的那一半的范围内，从而决定收缩哪边。
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // 左半有序
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半有序
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}这样同样是 O(log n)。
面试官：
“最后一类原地操作，比如‘找到所有数组中消失的数字（LeetCode 448）’，不用额外空间怎么做？”
我：
这题特别体现原地哈希的思想：利用数组下标做标记。
遍历每个数，把 |num|-1 位置上的数变成负数。第二遍扫描，如果某个位置 i 上的数还是正数，说明数字 i+1 没出现过。
for (int i = 0; i < nums.length; i++) {
int idx = Math.abs(nums[i]) - 1;
if (nums[idx] > 0) nums[idx] = -nums[idx];
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) res.add(i + 1);
}时间 O(n)，额外空间 O(1)，不破坏原数组数值关系（用符号位），算是一种很优雅的 trick ✨。
面试官（满意地点头）：
“不错，这六大套路总结得很到位，细节也抠得准。我这里还有一张你刚提到的题型的速查表，咱们一起看看，帮你巩固一下。”
| 套路 | 代表题 | 核心技巧 | 时间复杂度 |
|---|---|---|---|
| 遍历+统计 | 最大子数组和 (leetcode 53) | 滚动dp / 贪心 | O(n) |
| 双指针-对撞 | 盛水容器 (leetcode 11) | 排除短板 | O(n) |
| 双指针-快慢 | 删除重复项 (leetcode 26) | slow维护有效区 | O(n) |
| 滑动窗口 | 无重复最长子串 (leetcode 3) | 哈希记录最后位置+左边界跳跃 | O(n) |
| 前缀和+哈希 | 和为K的子数组 (leetcode 560) | pre-k 查询频次 | O(n) |
| 二分查找 | 搜索旋转数组 (leetcode 33) | 利用半区有序缩小 | O(log n) |
| 原地操作 | 消失的数字 (leetcode 448) | 下标原地哈希标记 | O(n) |
面试官（放下水杯，话锋一转）：
“刚才的六大套路分类很清晰，代码写得也到位。不过光会写还不够，我更想听听你对每个套路背后的技术难点是怎么理解的，以及你平时编码时怎么规避这些坑。来，挑几个重点说说。” 🧐
我：
好的面试官，我按刚才的六大类，逐个拆解一下难点和解决方案，顺便把对应的核心代码、技术亮点也贴出来，您看这样行不行。
🧩 第一类：遍历+统计
难点
- 如何只用
O(1)空间维护状态，而不引入额外数组。 - 摩尔投票(leetcode 169)中，当
count == 0时换候选人，容易写成错误的判断顺序。
解决方案
- 用滚动变量代替 DP 数组。
- 投票逻辑写成
if-else if结构，保证每次迭代只执行一个分支。
// 最大子数组和(leetcode 53) —— 滚动dp
public int maxSubArray(int[] nums) {
int dp = nums[0], max = nums[0];
for (int i = 1; i < nums.length; i++) {
dp = Math.max(nums[i], dp + nums[i]);
max = Math.max(max, dp);
}
return max;
}
// 摩尔投票(leetcode 169) —— 对拼消耗
public int majorityElement(int[] nums) {
int cand = nums[0], count = 1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) {
cand = nums[i];
count = 1;
} else if (nums[i] == cand) {
count++;
} else {
count--;
}
}
return cand;
}🐢🐇 第二类：双指针
难点
- 对撞指针：为什么移动短板不会错过最优解？容易写成移动长板。
- 快慢指针：
slow和fast的起始位置、更新逻辑容易错，尤其要去重时保留最多k个相同元素的情况。
解决方案
- 用排除法去理解移动短板：面积由短板决定，移动长板高度必然不变或变小，宽度必然变小，所以直接剪枝。
- 快慢指针固定套路：
slow指向有效区最后一个元素，fast遍历，符合条件才放到slow+1。
// 盛最多水的容器(leetcode 11) —— 对撞指针
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, max = 0;
while (i < j) {
int area = Math.min(height[i], height[j]) * (j - i);
max = Math.max(max, area);
if (height[i] < height[j]) i++;
else j--;
}
return max;
}
// 删除有序数组重复项（保留一个）(leetcode 26) —— 快慢指针
public int removeDuplicates(int[] nums) {
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}🪟 第三类：滑动窗口
难点
- 左边界
left如何直接跳跃而不是逐格移动，否则退化成O(n²)。 - 字符去重时，
index数组的初始值要设为-1，否则+1会下标错乱。
解决方案
- 用
int[128]记录字符最后出现位置，left = Math.max(left, index[c] + 1)一次性收缩到位。 - 初始化数组为
-1，或者统一偏移量。
// 无重复字符的最长子串(leetcode 3) —— 滑动窗口
public int lengthOfLongestSubstring(String s) {
int[] idx = new int[128];
Arrays.fill(idx, -1); // 技术亮点：初始-1，省去额外判断
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
left = Math.max(left, idx[c] + 1); // 关键跳跃
maxLen = Math.max(maxLen, right - left + 1);
idx[c] = right;
}
return maxLen;
}📏 第四类：前缀和+哈希
难点
- 公式推导
pre[j-1] = pre[i] - k容易写反，或者在HashMap中先查询还是先更新的顺序搞错（会导致 i < j 的条件不成立）。 - 边界条件
pre=0必须预先放入 map，且次数为1，否则会漏掉从数组开头开始的子数组。
解决方案
- 固定模板：先
count += map.get(sum - k)，再map.put(sum, ...)。 - 记得
map.put(0, 1)。
// 和为K的子数组(leetcode 560) —— 前缀和+哈希
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0, 1); // 技术亮点：前缀0占位
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}🔍 第五类：二分查找
难点
- 旋转数组二分：判断有序半区时，
nums[l] <= nums[mid]必须带等号，处理[3,1]这种仅两个元素的边界情况。 - 边界收缩条件：用
<=还是<，死循环风险。
解决方案
- 统一用
while (l <= r)，在循环内处理mid，找到直接返回。 - 先判断
nums[l] <= nums[mid]确定左半有序，再用target是否在该半区决定收缩。
// 搜索旋转排序数组(leetcode 33) —— 二分
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) { // 左半有序
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else { // 右半有序
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}🔄 第六类：原地操作
难点
- 原地哈希：如何用正负号标记而不丢失原本数组的数值？取绝对值访问是精髓。
- 轮转数组的三次反转法，边界计算（
k % n）容易写错。
解决方案
- 访问标记前先
int idx = Math.abs(nums[i]) - 1，修改时只对正数取反。 - 轮转先
k %= n，然后写一个reverse辅助方法。
// 找到所有消失的数字(leetcode 448) —— 原地哈希
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int idx = Math.abs(nums[i]) - 1; // 技术亮点：绝对值访问
if (nums[idx] > 0) nums[idx] = -nums[idx];
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) res.add(i + 1);
}
return res;
}
// 轮转数组 —— 三次反转
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
i++; j--;
}
}面试官（拿回简历，在角落记了两笔）：
“很好，难点梳理得很透彻，防坑意识很成熟。尤其是前缀和的查询顺序、摩尔投票的 if-else 分支、旋转数组二分的等号处理，这些都是线上写 bug 的高发区，你能提前点出来，说明确实刷题不光是背答案，是真理解了。💯”
“再考你一个扩展：如果我把数组改成 循环数组 或者 二维矩阵，你还记得怎么把这些套路迁移过去吗？我们留在下一轮系统设计前聊一下？”
📋 一维数组技术难点速查表
| 套路 | 核心难点 | 典型坑点 | 解决方案 |
|---|---|---|---|
| 遍历+统计 | O(1)空间维护状态 | 摩尔投票分支顺序错误 | 固定 if-else if 结构 |
| 对撞指针 | 为何移动短板不丢解 | 移动长板导致漏解 | 理解面积由短板决定的排除法 |
| 快慢指针 | slow/fast初始化与边界 | 保留k个重复元素逻辑复杂 | 模板化：slow指向有效区末尾 |
| 滑动窗口 | left一次跳跃到位 | 忘记初始化索引数组为-1 | Arrays.fill(idx, -1) |
| 前缀和+哈希 | 先查询后更新顺序 | 漏掉pre=0的边界 | map.put(0,1) 且先get再put |
| 二分查找 | 旋转数组判断有序半区 | 等号遗漏导致死循环 | nums[l] <= nums[mid] |
| 原地哈希 | 标记后不丢失原值 | 直接修改数值导致索引错 | 用 Math.abs(nums[i]) - 1 |
我：
谢谢面试官，我回去把循环数组和二维的套路也复盘一下，下次跟您接着聊 😄。