# 数组的应用——真题归纳与解读|算法篇

> 本文系统总结了数组在算法面试中的常见应用与解题思路，涵盖两数求和等高频真题，详细分析了常见解法、优化技巧及面试考点，帮助读者高效掌握数组相关算法题的解题方法与思维提升。

- 原文：https://feinterview.poetries.top/docs/algorithm/algorithm-interview/06-%E6%95%B0%E7%BB%84%E7%9A%84%E5%BA%94%E7%94%A8%E2%80%94%E2%80%94%E7%9C%9F%E9%A2%98%E5%BD%92%E7%BA%B3%E4%B8%8E%E8%A7%A3%E8%AF%BB
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2026.10.03
- 可见范围：免费部分

---

我们现在要开始做题啦！

万里长征第一步，仍然是数组。
单纯针对数组来考察的题目，总体来说，都不算太难——数组题目要想往难了出，基本都要结合排序、二分和动态规划这些相对复杂的算法思想才行。

咱们本节要解决的正是这一类“不算太难”的数组题目——并不是只有难题才拥有成为真题的入场券，一道好题不一定会难，它只要能够反映问题就可以了。

本节所涉及的题目在面试中普遍具有较高的出镜率、同时兼具一定的综合性，对培养大家的通用解题能力大有裨益 。

相信这节你会学得很开心，在轻松中收获自己的第一份算法解题锦囊。

## Map 的妙用——两数求和问题

- 暴力两层循环 `O(n²)`；用 `Map` 记「值 → 下标」，变成一次遍历 `O(n)`、空间 `O(n)`
- 求和转求差：看到 `x` 就去查 `target - x` 出现过没有
- 顺序必须是先查后存，`Map` 里只放当前下标之前的数，才不会自己配自己
- 用 `Map.has()` 判存在，别用对象加 `if (obj[k])`，下标 `0` 是假值
- `[3, 3]` 凑 `6` 是合法的，两个不同位置就行

**两数之和的套路是拿空间换时间：一边遍历一边用 `Map` 记下见过的数和下标，每到一个数就去查它的「另一半」在不在。** 比如 `nums = [2, 7, 11, 15]`、`target = 9`，到 `7` 时查 `9 - 7 = 2`，`Map` 里有，下标 `0`，直接返回 `[0, 1]`。顺序很关键，一定是先查再存，不然 `[3, 3]` 找 `6` 时第一个 `3` 会和自己配对。时间从 `O(n²)` 降到 `O(n)`，代价是 `O(n)` 的额外空间。

哈希解法的不变量是：进入第 `i` 轮时，`seen` 只保存区间 `[0, i)` 的值及下标。因此命中补数时，它一定来自不同元素；未命中才写入当前值。原文使用对象并用 `!== undefined` 判断，会把“索引值是否存在”和“属性值是否为 undefined”混在一起，使用 `Map.has()` 更直接。

```js
function twoSum(nums, target) {
  const seen = new Map()
  for (let i = 0; i < nums.length; i += 1) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}
```

每个元素最多查询和写入一次，期望时间 `O(n)`、额外空间 `O(n)`。若要求全部不重复下标组合，`Map<number, number>` 不够，需要保存每个值的下标列表或采用另一套去重契约；若输入含浮点数，还要先确认能否直接用精确相等比较。

> 真题描述： 给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

```
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
```

- **为什么用 `Map` 而不是普通对象 `{}`？**

  对象的键会被转成字符串，还可能撞上 `toString` 这类原型属性。`Map` 键保留原始类型，`has`、`get`、`set` 语义也清楚，算法题我默认用它。

- **代码里写 `if (seen[need])` 判断命中，哪里有坑？**

  下标 `0` 是假值，补数正好在第一个位置时会被判成没找到。改成 `seen.has(need)`，或者至少 `seen[need] !== undefined`。

- **题目改成要返回所有满足条件的下标对，还能一次遍历吗？**

  能遍历一次，但 `Map` 要改成 `Map<number, number[]>`，每个值存所有出现过的下标，命中时和每一个都配一对。注意结果本身可能有 `O(n²)` 对，比如全是同一个数，输出成本就不是线性了。

- **金额是 `0.1`、`0.2`，目标 `0.3`，为什么永远找不到？**

  `0.3 - 0.1` 在浮点里等于 `0.19999999999999998`，和 `Map` 里的 `0.2` 对不上，哈希只认精确相等。金额先换成分的整数再做，别临时加个 `epsilon`。

- **数组已经有序了，还用 `Map` 吗？**

  有序就用左右指针：和小了左指针右移，大了右指针左移，`O(n)` 时间、`O(1)` 空间，比 `Map` 省内存。

### 思路分析：

- 看到两层循环先想：能不能用空间换时间压成一层
- 求和变求差：`Map` 存「已见过的值 → 下标」，查 `target - nums[i]`
- 先查补数再写当前值，命中返回两个下标
- 平均 `O(n)` 时间、`O(n)` 空间
- 对象模拟时用 `!== undefined` 判断，更推荐直接 `Map.has()`

**这题我会把「找两个数加起来等于 `target`」换成「对每个数，查它差的那个数之前出现过没有」。** 遍历时 `Map` 里只放当前位置之前的数，所以要先查 `target - nums[i]`，没查到再把自己放进去，这样同一个元素不会被用两次。双层循环是 `O(n²)`，数据上万就开始明显慢；`Map` 版一趟走完，`O(n)`，多花的就是一张表的内存。教程里用对象写也能过，但判断要写成 `!== undefined`，我更习惯直接用 `Map.has()`，省得被下标 `0` 坑。

```mermaid
sequenceDiagram
    autonumber
    participant L as 遍历循环
    participant M as Map 已见过的值
    L->>M: i=0 值 2，查补数 7
    M-->>L: 没有
    L->>M: 存入 2 对应下标 0
    L->>M: i=1 值 7，查补数 2
    alt 补数存在
        M-->>L: 命中，下标 0
        L-->>L: 返回 0 和 1，结束
    else 补数不存在
        M-->>L: 没有
        L->>M: 存入 7 对应下标 1，继续下一轮
    end
    Note over L,M: 先查后存，Map 里永远只有当前下标之前的数
```

**一个“淳朴”的解法**

> 这道题相信很多同学看一眼就很快能得出一个最基本的思路：两层循环来遍历同一个数组；第一层循环遍历的值记为 a，第二层循环时遍历的值记为 b；若 a+b = 目标值，那么 a 和 b 对应的数组下标就是我们想要的答案。

**对“淳朴”解法的反思**

大家以后做算法题的时候，要有这样的一种本能：当发现自己的代码里有两层循环时，先反思一下，能不能用空间换时间，把它优化成一层循环。

> 因为两层循环很多情况下都意味着 `O(n^2)` 的复杂度，这个复杂度非常容易导致你的算法超时。即便没有超时，在明明有一层遍历解法的情况下，你写了两层遍历，面试官对你的印象分会大打折扣。

**空间换时间，Map 来帮忙**

拿我们这道题来说，其实二层遍历是完全不必要的。

> 大家记住一个结论：几乎所有的求和问题，都可以转化为求差问题。 这道题就是一个典型的例子，通过把求和问题转化为求差问题，事情会变得更加简单。

我们可以在遍历数组的过程中，增加一个 Map 来记录已经遍历过的数字及其对应的索引值。然后每遍历到一个新数字的时候，都回到 `Map` 里去查询 `targetNum` 与该数的差值是否已经在前面的数字中出现过了。若出现过，那么答案已然显现，我们就不必再往下走了。

我们以 `nums = [2, 7, 11, 15]` 这个数组为例，来模拟一下这个思路：

第一次遍历到 `2`，此时 `Map` 为空：

![](https://s.poetries.top/images/20210905111542.png)

以 `2` 为 `key`，索引 0 为 value 作存储，继续往下走；遇到了 7：

![](https://s.poetries.top/images/20210905111602.png)

计算 targetNum 和 7 的差值为2，去 Map 中检索 2 这个 key，发现是之前出现过的值：

![](https://s.poetries.top/images/20210905111610.png)

那么 2 和 7 的索引组合就是这道题的答案啦。

键值对存储我们可以用 ES6 里的 Map 来做，如果图省事，直接用对象字面量来定义也没什么问题

编码实现

```js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    // 这里我用对象来模拟 map 的能力
    const diffs = {}
    // 缓存数组长度
    const len = nums.length
    // 遍历数组
    for(let i=0;i<len;i++) {
        // 判断当前值对应的 target 差值是否存在（是否已遍历过）
        if(diffs[target-nums[i]]!==undefined) {
            // 若有对应差值，那么答案get！
            return [diffs[target - nums[i]], i]
        }
        // 若没有对应差值，则记录当前值
        diffs[nums[i]]=i
    }
};
```

> tips：这道题也可以用 ES6 中的 Map 来做，你试试呢？

- **候选人写了双层循环，说数据量不大不用优化，你会怎么接？**

  我会问他数据涨到 `10` 万条会怎样：`n²` 是 `100` 亿级的比较，直接超时。能一层解决的写两层，面试里印象分会掉，至少要说出 `Map` 的思路。

- **`[3, 3]` 找 `6`，代码先 `set` 当前值再查补数，会返回什么？**

  第一轮存了 `3 → 0`，马上查 `3` 就命中自己，返回 `[0, 0]`。顺序换成先查后存，第二轮才会返回正确的 `[0, 1]`。

- **要返回所有组合，但现在是 `Map<number, number>`、命中就 `return`，改哪两处？**

  一是值改成下标数组，不然同值的旧下标会被覆盖；二是命中后别 `return`，把组合收集起来继续走。

- **用对象模拟 `Map`，日志里补数明明存在却没命中，查什么？**

  先看判断是不是写成了真假值判断，下标 `0` 会被吞掉。再看键是不是被字符串化后和别的东西撞了，比如输入里混进了字符串 `'2'` 和数字 `2`，在对象里是同一个键。

- **数组已经按价格排好序，只问有没有一对等于预算，选 `Map` 还是双指针？**

  双指针，`O(1)` 额外空间。但如果要返回原始下标，而数组是你自己排的序，就得把下标绑在值上一起排，不能把排序后的位置当原位置返回。

- **有人把代码改成先执行 `diffs[nums[i]] = i` 再判断补数，`[3, 3]` 目标 `6` 会错在哪？**

  第一轮刚写进 `3 → 0`，接着查 `3` 就命中了自己，返回 `[0, 0]`。查询必须在写入前面，`diffs` 才只代表已经走过的部分。

- **`0.1 + 0.2` 凑 `0.3` 查不到，加个 `epsilon` 行不行？**

  不行，`Map` 只做精确匹配，`epsilon` 没法用在键上，非要用就只能退回遍历比较。正确做法是按币种精度转成最小单位整数，比如乘 `100` 后用 `Math.round` 取整再建表。

- **从返回任意一组改成返回全部，大量重复值时为什么会漏？**

  单值映射里同一个数只留最后一个下标，前面的被覆盖了，再加上命中就 `return`，后面的也不看了。改成存下标数组，并且走完整个数组。

- **线上返回了 `[undefined, 4]`，代码是 `if (diffs[c])` 判断的，怎么回事？**

  按真假值判断，命中时取到的一定是真值，不可能是 `undefined`，所以判断和取值用的多半不是同一个键，比如判断写 `diffs[target - nums[i]]`、取值写成了 `diffs[nums[i] - target]`。顺带它还会把下标 `0` 当成没找到。先抽一个 `const need = target - nums[i]`，再统一换成 `Map.has(need)` 加 `Map.get(need)`。

- **移动端内存紧张、数组又是无序的，用哈希还是先排序再双指针？**

  排序是 `O(n log n)`，但 `JS` 里排完要原下标就得建 `[值, 下标]` 对象数组，内存不一定比 `Map` 省。只要求返回任意一组下标的话，我还是选哈希，一趟出结果。

## 强大的双指针法

- 双指针厉害的地方是每走一步都能排除一批不可能的候选，不是「声明两个变量」
- 对撞指针：一般要求有序，和小了左边右移，和大了右边左移
- 快慢 / 同向指针：去重、滑动窗口、读写分离、链表找中点
- 先想清楚每个指针代表什么，再写不变量和终止条件
- 为了用双指针先排序，要把 `O(n log n)`、改动原数组、丢原下标算进去

**双指针真正的价值是利用有序这类单调关系，每移动一次就安全地排除一段候选，所以不用回头。** 形态不止一种：三数之和是固定一个数，左右指针往中间夹；合并有序数组是两个读指针从尾部往前，再加一个写指针；数组去重是快指针读、慢指针写。写之前我会先说清楚每个指针代表什么，比如 `[0, slow)` 是已经去重好的部分，这样边界和终止条件就不容易写错。

双指针不是固定模板。合并有序数组时，两个读指针分别指向尚未合并部分的最大值，写指针指向最终数组的空位；三数之和则固定一个值，让左右边界根据当前和单向收缩。两者共享的核心是：移动后，被越过的元素已有数学依据不再成为候选。

- **候选人说双指针就是一左一右往中间走，你怎么反驳？**

  那只是对撞指针。原地去重是一快一慢同向走：`fast` 往前读，遇到新值才写到 `slow` 位置。合并有序数组甚至是两个读指针加一个写指针。共同点是指针只往一个方向走、不回退。

- **无序数组直接用左右指针找目标和，有时对有时错，为什么？**

  无序时，和偏大就左移右指针，没法保证被扔掉的那个数不会和别的数凑成答案，移动没有依据。要么先排序，要么用 `Map` 查补数。

- **用快慢指针给有序数组原地去重，代码怎么写？**

  `let slow = 0; for (let fast = 1; fast < n; fast++) if (nums[fast] !== nums[slow]) nums[++slow] = nums[fast]`，最后长度是 `slow + 1`。不变量是 `[0, slow]` 里都是不重复的值。

- **合并有序数组和三数之和都是双指针，能抽一个通用模板吗？**

  不建议。一个关心安全写入的位置，一个关心当前和跟目标的大小，状态和终止条件都不一样，硬抽象只会把边界藏起来。共用的是思路，不是代码。

### 合并两个有序数组

- `nums1` 前 `m` 个才是有效数据，后面的 `0` 是占位空位
- 从尾部比较，大的往 `nums1` 末尾填，写的都是空位，不会覆盖还没读的数
- 三个指针：`i = m-1`、`j = n-1`、`k = m+n-1`
- 循环条件 `while (j >= 0)` 就够：`nums2` 剩余要复制，`nums1` 剩余本来就在原位
- 时间 `O(m+n)`、额外空间 `O(1)`，会直接改 `nums1`

---

> 以上是免费部分。完整内容需要「前端进阶之旅」会员，原文：https://feinterview.poetries.top/docs/algorithm/algorithm-interview/06-%E6%95%B0%E7%BB%84%E7%9A%84%E5%BA%94%E7%94%A8%E2%80%94%E2%80%94%E7%9C%9F%E9%A2%98%E5%BD%92%E7%BA%B3%E4%B8%8E%E8%A7%A3%E8%AF%BB
