手帐 Blog

主题

04 · 数组基础题手感 ​

目标：独立完成移除元素、合并有序数组、加一等经典 Easy，建立「原地改数组」的手感。

为什么面试会考 ​

数组题是前端算法的基本盘。公司常考：

  • 原地操作：不新开大数组，用读写指针。
  • 边界：空数组、全删、进位。
  • 有序合并：从后往前填，避免覆盖。

这三题覆盖上述考点，刷透后面双指针、滑动窗口更顺。

零基础概念：读写指针（原地改数组） ​

很多题要求「原地」修改，意思是在原数组上覆盖，不另开同等长度数组。

text
读指针 read：扫描每一个元素
写指针 write：下一个有效元素该放哪

模板：

javascript
let write = 0;
for (let read = 0; read < nums.length; read++) {
  if (/* 保留条件 */) {
    nums[write] = nums[read];
    write++;
  }
}
// write 即为新长度

零基础概念：从后往前合并 ​

两个有序数组合并到一个数组里，若从前往后填，会把还没读的元素盖住。
从尾部往前填，每次取较大的放到 tail。

JS 模板 / 套路 ​

题型套路
移除元素写指针收集「不等于 val」的
合并有序数组三指针从后往前
加一从末位进位，可能最高位 +1

精讲 1：LeetCode 27. 移除元素 ​

题意：原地移除所有等于 val 的元素，返回新长度。元素顺序可改变。

javascript
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== val) {
      nums[write] = nums[read];
      write++;
    }
  }
  return write;
};
  • 时间 O(n)，空间 O(1)。
  • 前 write 个元素即为结果，后面不用管。

精讲 2：LeetCode 88. 合并两个有序数组 ​

nums1 有足够空间，m 为有效长度；nums2 长度 n。合并进 nums1。

javascript
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
  let i = m - 1;      // nums1 有效末尾
  let j = n - 1;      // nums2 末尾
  let tail = m + n - 1; // 填充位置

  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[tail] = nums1[i];
      i--;
    } else {
      nums1[tail] = nums2[j];
      j--;
    }
    tail--;
  }
};
  • 为何 while (j >= 0)：nums2 剩的才必须填；nums1 剩的已在正确位置。
  • 时间 O(m+n)，空间 O(1)。

精讲 3：LeetCode 66. 加一 ​

非负整数用数组表示，最高位在左。加一后返回新数组（可能进位多一位）。

javascript
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;
      return digits;
    }
    digits[i] = 0;
  }
  return [1, ...digits];
};
  • 末位不是 9：直接 +1 返回。
  • 全是 9：[9,9,9] → [1,0,0,0]，前面补 1。

练习清单 ​

题号一句话提示
LeetCode 26. 删除有序数组中的重复项写指针，相同则跳过
LeetCode 283. 移动零先把非零前移，后面填 0
LeetCode 905. 按奇偶排序数组双指针交换奇偶
LeetCode 977. 有序数组的平方原数组有序，平方后两头大，双指针从后填
LeetCode 118. 杨辉三角模拟，每行由上一行相邻相加

今日验收 checklist ​

  • [ ] 三篇精讲题均在 LeetCode 用 JS 提交通过
  • [ ] 能画出 88 题「从后往前」为何不会覆盖
  • [ ] 能默写 27 题读写指针框架
  • [ ] 练习清单再独立完成 1～2 道

若你以前见过 ​

蓝桥数组题常考模拟与下标，思路相通。LeetCode 强调原地与返回值是新长度（27、26），提交前看清题目要不要改原数组、返回什么。