跳到主要内容

数组✅

本章准确的说不算算法内容，只是针对数组常用操作做一些说明，

说一下 Array 的常用方法?​

答案

延伸阅读

数组合并？​

给定两个有序数组 s1、s2, 将 s1 和 s2 合并成一个有序数组。注意 s1 的长度可以容纳 s2 的所有元素。

const s1 = [1, 3, 5, 6, undefined, undefined, undefined]
const s2 = [3, 10]

function mergeArrays (arr1, arr2) {

}
答案
exports.mergeArrays = function mergeArrays(arr1, arr2) {
  let i = arr1.length - arr2.length - 1;
  let j = arr2.length - 1;
  let k = arr1.length - 1;

  while (j >= 0) {
    if (i >= 0 && arr1[i] > arr2[j]) {
      arr1[k--] = arr1[i--];
    } else {
      arr1[k--] = arr2[j--];
    }
  }
  return arr1;
}

Open browser consoleTests

三数求和？​

给定数组 s1, 返回所有 array[i, j, k] 的和为 0 的解，对应索引组成的集合

const s1 = [-1, -2, 1, 2, 0]

function threeSum (arr) {

}
答案
exports.threeSum = function threeSum(arr) {
  arr.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < arr.length - 2; i++) {
    if (i > 0 && arr[i] === arr[i - 1]) continue;
    let left = i + 1;
    let right = arr.length - 1;
    while (left < right) {
      const sum = arr[i] + arr[left] + arr[right];
      if (sum === 0) {
        result.push([arr[i], arr[left], arr[right]]);
        while (arr[left] === arr[left + 1]) left++;
        while (arr[right] === arr[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

Open browser consoleTests

两数求和问题？​

给定一个数组 S 和一个整数 target，在数组 S 中找到两个数，使得它们的和等于 target。例如

const s1 = [1, 3, 5, 6]
const target = 9

function twoSum (arr, target) {

}
答案
exports.twoSum = function twoSum(arr, target) {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (map.has(complement)) {
      return [complement, arr[i]];
    }
    map.set(arr[i], i);
  }
  return [];
}

Open browser consoleTests

最大子数组和​

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

function maxSubArray (nums) {

}
答案
function maxSubArray (nums) {
  let maxSum = nums[0]
  let currentSum = nums[0]
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i])
    maxSum = Math.max(maxSum, currentSum)
  }
  return maxSum
}

module.exports = maxSubArray

Open browser consoleTests

寻找数组中的第 k 大元素​

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

const nums = [3, 2, 1, 5, 6, 4]
const k = 2

function findKthLargest (nums, k) {

}
答案
function findKthLargest (nums, k) {
  nums.sort((a, b) => b - a)
  return nums[k - 1]
}

module.exports = findKthLargest

Open browser consoleTests

Fizz Buzz 问题​

答案

核心概念 经典条件判断算法题（LeetCode 412）：从 1 到 n 遍历：

  • 若同时是 3 和 5 的倍数（即 15 的倍数），输出 "FizzBuzz"。
  • 若仅是 3 的倍数，输出 "Fizz"；若是 5 的倍数，输出 "Buzz"。
  • 否则输出数字字符串本身。

代码实现：

function fizzBuzz (n) {
  const result = []
  for (let i = 1; i <= n; i++) {
    const divBy3 = i % 3 === 0
    const divBy5 = i % 5 === 0

    if (divBy3 && divBy5) {
      result.push('FizzBuzz')
    } else if (divBy3) {
      result.push('Fizz')
    } else if (divBy5) {
      result.push('Buzz')
    } else {
      result.push(String(i))
    }
  }
  return result
}

// 复杂度分析
// 时间复杂度：O(n)
// 空间复杂度：O(1)（除返回值外）

面试官视角

  • 考察代码整洁度与判断顺序（必须先判断 15 的倍数，或通过字符串拼接 let s = ''; if (div3) s += 'Fizz'; if (div5) s += 'Buzz'; 提高扩展性）。

寻找首次匹配子序列​

答案

核心概念 在主数组 arr 中寻找子序列 subseq 首次出现的起始索引：

  • 如果要求连续子数组匹配，采用滑动窗口或双指针逐个比较，或者 KMP 算法。
  • 如果要求非连续但相对顺序一致的子序列，使用贪心双指针匹配。

连续子数组匹配实现（类似 indexOf / strStr）：

function findSubsequence (arr, subseq) {
  const m = arr.length
  const n = subseq.length
  if (n === 0) return 0
  if (m < n) return -1

  for (let i = 0; i <= m - n; i++) {
    let match = true
    for (let j = 0; j < n; j++) {
      if (arr[i + j] !== subseq[j]) {
        match = false
        break
      }
    }
    if (match) return i
  }

  return -1
}

// 验证
console.log(findSubsequence([1, 2, 3, 4, 5], [3, 4])) // 2
console.log(findSubsequence([1, 2, 3], [4])) // -1

面试官视角

  • 考查双指针边界判断（i <= m - n）与滑动窗口思想。

移动零​

答案

核心概念 LeetCode 283 原题：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  • 约束要求：必须在不复制数组的情况下**原地（in-place）**对数组进行操作，空间复杂度为 $O(1)$。
  • 解题思路（双指针一次遍历）：维护指针 slow 指向当前第一个为 0 的位置，快指针 fast 遍历数组。当 nums[fast] !== 0 时，将其与 nums[slow] 交换，并将 slow 右移。

代码实现：

function moveZeroes (nums) {
  let slow = 0

  // 1. 将所有非零元素按顺序移动到前面
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      if (slow !== fast) {
        // 交换非零元素与 slow 处的 0
        const temp = nums[slow]
        nums[slow] = nums[fast]
        nums[fast] = temp
      }
      slow++
    }
  }

  return nums
}

// 验证
const list = [0, 1, 0, 3, 12]
moveZeroes(list)
console.log(list) // [1, 3, 12, 0, 0]

复杂度分析

  • 时间复杂度：$O(n)$，只需遍历一次数组。
  • 空间复杂度：$O(1)$，无任何额外数组开销。

面试官视角

  • 考查对双指针（快慢指针）原地调整数组顺序的熟练程度，交换优化避免了二次循环重写 0 的步骤。