小落叶的个人知识库

外观

📖预计阅读时长：0 分钟字数：0

代码随想录 — 数组与双指针 ​

对应 leetcode-master：数组理论基础、704 二分、27 移除元素、977/209、59 螺旋矩阵 等。

一、数组理论基础（有助于理解题目的前提） ​

  • 定义：数组是存放在连续内存空间上的相同类型数据的集合。
  • 下标从 0 开始，通过下标 O(1) 访问。
  • 关键点：因为地址连续，删除/插入需要移动后面元素；在实现上元素只能覆盖不能真正删除（如「移除元素」用双指针覆盖）。
  • 二维数组：C++ 中二维数组在内存中连续；Java 等语言可能每行是独立对象，行与行之间不一定连续，了解即可。

面试中的意义：数组题想法往往简单，难点在于对边界和代码的掌控（例如二分、双指针的区间定义）。

二、二分查找（704） ​

前提：有序、无重复（或有重复但题目允许任一下标）。

核心：区间定义是不变量。写的时候先定一种区间（左闭右闭 或 左闭右开），全程按同一种处理边界。

写法一：左闭右闭 [left, right] ​

  • right = nums.length - 1，区间包含两端。
  • while (left <= right)：因为 left == right 时区间仍有效。
  • nums[middle] > target → 在左半段，right = middle - 1（当前 middle 已排除）。
  • nums[middle] < target → 在右半段，left = middle + 1。

写法二：左闭右开 [left, right) ​

  • right = nums.length，区间不包含 right。
  • while (left < right)：left == right 时区间已空。
  • nums[middle] > target → right = middle（下一轮不会再看 middle）。
  • nums[middle] < target → left = middle + 1。

防溢出：middle = left + ((right - left) >> 1) 或 left + Math.floor((right - left) / 2)。

易错：混用两种区间（例如一边写 right = middle - 1 一边写 while (left < right)）容易死循环或漏掉答案，选定一种写法并坚持。

三、双指针 — 移除元素（27） ​

题意：原地删除值等于 val 的元素，返回新长度。

思路：快慢指针。快指针遍历数组，慢指针表示「下一个要保留元素该放的位置」；当 nums[fast] !== val 时，把 nums[fast] 赋给 nums[slow] 并 slow++。这样等于用后面的非 val 覆盖前面的 val，实现「删除」。

  • 时间 O(n)，空间 O(1)。
  • 理解：数组元素只能覆盖，不能真删；双指针把「保留的」挤到前面，逻辑上等价于删除。

四、双指针 — 有序数组的平方（977） ​

题意：非递减数组，每个数平方后仍要非递减输出。

思路：平方后最大的一定在两端。用左右双指针从两端向中间走，比较平方值，把较大的放入结果数组的从后往前的位置，直到两指针相遇。这样一次遍历即可，无需先平方再排序。

五、滑动窗口 — 长度最小的子数组（209） ​

题意：正整数数组，找和 ≥ target 的长度最小的连续子数组。

思路：滑动窗口。右指针扩张以增大和，当和 ≥ target 时，尝试收缩左指针以减小长度并更新最小长度；每次右指针右移后，在满足和 ≥ target 的前提下尽量左移左指针。

  • 关键：窗口内是连续子数组，右扩、左缩都要维护当前和。
  • 若从未出现和 ≥ target，返回 0。

六、螺旋矩阵（59） ​

题意：生成 n×n 的 1 到 n² 的螺旋矩阵。

思路：按「上 → 右 → 下 → 左」一圈一圈填；每圈用四个循环，并维护 left, right, top, bottom 边界。每填完一条边就收缩对应边界；若 n 为奇数，最后可能剩一个中心点单独处理。

易错：边界开闭要统一（例如左闭右开），否则重复填或越界；循环条件要写 left <= right && top <= bottom 等，避免多跑一圈。

javascript
// 螺旋读取矩阵（LeetCode 54）
   function spiralOrder(matrix) {
     if (!matrix.length || !matrix[0].length) return [];
     let top = 0, bottom = matrix.length - 1;
     let left = 0, right = matrix[0].length - 1;
     const res = [];

     while (top <= bottom && left <= right) {
       for (let j = left; j <= right; j++)
  res.push(matrix[top][j]);
       top++;
       for (let i = top; i <= bottom; i++)
  res.push(matrix[i][right]);
       right--;
       if (top <= bottom) {
         for (let j = right; j >= left; j--)
  res.push(matrix[bottom][j]);
         bottom--;
       }
       if (left <= right) {
         for (let i = bottom; i >= top; i--)
  res.push(matrix[i][left]);
         left++;
       }
     }
     return res;
   }

   // 螺旋生成矩阵（LeetCode 59）
   function generateMatrix(n) {
     const matrix = Array.from({ length: n }, () =>
  Array(n).fill(0));
     let top = 0, bottom = n - 1;
     let left = 0, right = n - 1;
     let val = 1;

     while (top <= bottom && left <= right) {
       for (let j = left; j <= right; j++) matrix[top][j] = val++;
       top++;
       for (let i = top; i <= bottom; i++) matrix[i][right] =
  val++;
       right--;
       if (top <= bottom) {
         for (let j = right; j >= left; j--) matrix[bottom][j] =
  val++;
         bottom--;
       }
       if (left <= right) {
         for (let i = bottom; i >= top; i--) matrix[i][left] =
  val++;
         left++;
       }
     }
     return matrix;
   }

七、数组总结 ​

题型要点
二分先定区间（左闭右闭 / 左闭右开），再写边界，坚持循环不变量
双指针快慢指针（覆盖/删除）、左右指针（有序、两数之和类）
滑动窗口连续子数组/子串，右扩满足条件、左缩找最优，维护窗口内信息
模拟螺旋矩阵等，统一边界、按圈或按层处理

建议：二分和「移除元素」一定要手写熟练，很多题是在此基础上的变形（如查找插入位置、旋转数组中的查找等）。

附：核心代码模板 ​

二分查找（左闭右闭） ​

javascript
// JavaScript
function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
python
# Python
def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

快慢双指针 — 移除元素 ​

javascript
// JavaScript — 时间 O(n)，空间 O(1)
function removeElement(nums, val) {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      nums[slow++] = nums[fast];
    }
  }
  return slow;
}

滑动窗口 — 最小子数组长度 ​

javascript
// JavaScript — 时间 O(n)
function minSubArrayLen(target, nums) {
  let left = 0, sum = 0, res = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      res = Math.min(res, right - left + 1);
      sum -= nums[left++];
    }
  }
  return res === Infinity ? 0 : res;
}

Copyright@ 2024 Luoye Zero