前端面试知识库

Appearance

数组与字符串专题 ​

数组和字符串是算法面试的重中之重，掌握双指针、滑动窗口、哈希表三大技巧

📊 题目总览 ​

题目难度梯队关键技巧
两数之和⭐⭐第一梯队哈希表
最大子序和⭐⭐第一梯队Kadane算法
无重复字符最长子串⭐⭐⭐第二梯队滑动窗口
三数之和⭐⭐第三梯队排序+双指针
盛水容器⭐⭐进阶双指针
接雨水⭐⭐⭐进阶双指针/单调栈
搜索旋转排序数组⭐⭐进阶二分查找
最小覆盖子串⭐⭐⭐进阶滑动窗口
岛屿数量⭐⭐进阶DFS/BFS

1. 两数之和 ​

LeetCode: 1. 两数之和 | 难度: 简单 | 梯队: 第一梯队 ✅

题目描述 ​

给定一个整数数组 nums 和一个目标值 target，请找出和为目标值的两个整数的下标。

核心思路 ​

使用哈希表存储已遍历的数字及其索引，每次检查 target - 当前值 是否存在。

代码实现 ​

javascript
/**
 * 两数之和
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (map.has(complement)) {
      return [map.get(complement), i];
    }

    map.set(nums[i], i);
  }

  return [];
}

示例调用 ​

javascript
// 基础示例
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

// 答案不在开头
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

// 边界条件：两个相同的数
console.log(twoSum([3, 3], 6)); // [0, 1]

// 边界条件：负数
console.log(twoSum([-1, -2, -3, -4, -5], -8)); // [2, 4]

// 边界条件：包含0
console.log(twoSum([0, 4, 3, 0], 0)); // [0, 3]

// 边界条件：无解
console.log(twoSum([1, 2, 3], 7)); // []

复杂度分析 ​

  • 时间: O(n)
  • 空间: O(n)

2. 最大子序和 ​

LeetCode: 53. 最大子数组和 | 难度: 中等 | 梯队: 第一梯队 ✅

题目描述 ​

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

核心思路 ​

Kadane 算法：遍历时维护当前子数组的最大和，若当前和为负则重新开始。

代码实现 ​

javascript
/**
 * 最大子序和 - Kadane 算法
 * @param {number[]} nums
 * @return {number}
 */
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;
}

/**
 * DP 写法（更易理解）
 * dp[i] = 以 nums[i] 结尾的最大子数组和
 */
function maxSubArrayDP(nums) {
  const dp = new Array(nums.length);
  dp[0] = nums[0];

  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
  }

  return Math.max(...dp);
}

示例调用 ​

javascript
// 基础示例
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 ([4,-1,2,1])

// 边界条件：全是正数
console.log(maxSubArray([1, 2, 3, 4])); // 10

// 边界条件：全是负数
console.log(maxSubArray([-1, -2, -3])); // -1

// 边界条件：单个元素
console.log(maxSubArray([5])); // 5
console.log(maxSubArray([-5])); // -5

// 边界条件：包含0
console.log(maxSubArray([0, -1, 2])); // 2

复杂度分析 ​

  • 时间: O(n)
  • 空间: O(1)（Kadane）/ O(n)（DP）

3. 无重复字符最长子串 ​

LeetCode: 3. 无重复字符的最长子串 | 难度: 中等 | 梯队: 第二梯队

题目描述 ​

给定一个字符串 s，请找出其中不含重复字符的最长子串的长度。

核心思路 ​

滑动窗口：右指针扩展窗口，遇到重复字符时移动左指针缩小窗口。

代码实现 ​

javascript
/**
 * 无重复字符最长子串
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstring(s) {
  const map = new Map();  // char -> 最新索引
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // 如果字符已存在且在窗口内，移动左边界
    if (map.has(char) && map.get(char) >= left) {
      left = map.get(char) + 1;
    }

    map.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

示例调用 ​

javascript
// 基础示例
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")

// 全部相同
console.log(lengthOfLongestSubstring("bbbbb")); // 1

// 不重复
console.log(lengthOfLongestSubstring("abcd")); // 4

// 边界条件：空字符串
console.log(lengthOfLongestSubstring("")); // 0

// 边界条件：单字符
console.log(lengthOfLongestSubstring("a")); // 1

// 边界条件：包含空格和特殊字符
console.log(lengthOfLongestSubstring("ab c!d")); // 6

// 边界条件：最长在中间
console.log(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")

复杂度分析 ​

  • 时间: O(n)
  • 空间: O(min(n, m))，m 为字符集大小

4. 三数之和 ​

LeetCode: 15. 三数之和 | 难度: 中等 | 梯队: 第三梯队

题目描述 ​

给定整数数组 nums，判断是否存在三个元素使其和为 0。找出所有满足条件且不重复的三元组。

核心思路 ​

排序 + 双指针：固定第一个数，用双指针在剩余区间找两数之和。

代码实现 ​

javascript
/**
 * 三数之和
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
  const result = [];
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    // 剪枝：最小值大于0，不可能和为0
    if (nums[i] > 0) break;
    
    // 跳过重复元素
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        // 跳过重复元素
        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 result;
}

示例调用 ​

javascript
// 基础示例
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// 输出: [[-1, -1, 2], [-1, 0, 1]]

// 边界条件：无解
console.log(threeSum([0, 1, 1])); // []

// 边界条件：全是0
console.log(threeSum([0, 0, 0, 0])); // [[0, 0, 0]]

// 边界条件：少于3个元素
console.log(threeSum([1, 2])); // []

// 边界条件：刚好3个元素
console.log(threeSum([-1, 0, 1])); // [[-1, 0, 1]]

// 边界条件：大量重复
console.log(threeSum([-2, 0, 0, 2, 2])); // [[-2, 0, 2]]

复杂度分析 ​

  • 时间: O(n²)
  • 空间: O(log n) 排序

5. 盛水容器 ​

LeetCode: 11. 盛最多水的容器 | 难度: 中等

题目描述 ​

给定 n 个非负整数 height，每个数代表坐标中的一个点 (i, height[i])。找出两条线组成的容器能容纳最多的水。

核心思路 ​

双指针：从两端向中间移动，每次移动较短的边（移动较长边只会减小面积）。

代码实现 ​

javascript
/**
 * 盛最多水的容器
 * @param {number[]} height
 * @return {number}
 */
function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const h = Math.min(height[left], height[right]);
    const w = right - left;
    maxWater = Math.max(maxWater, h * w);

    // 移动较短的边
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxWater;
}

示例调用 ​

javascript
// 基础示例
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

// 边界条件：两个元素
console.log(maxArea([1, 1])); // 1

// 边界条件：递增数组
console.log(maxArea([1, 2, 3, 4, 5])); // 6

// 边界条件：递减数组
console.log(maxArea([5, 4, 3, 2, 1])); // 6

// 边界条件：包含0
console.log(maxArea([0, 2, 0, 3, 0])); // 6

复杂度分析 ​

  • 时间: O(n)
  • 空间: O(1)

6. 接雨水 ​

LeetCode: 42. 接雨水 | 难度: 困难

可视化演示：点击查看算法动画

题目描述 ​

给定 n 个非负整数 height，每个数代表坐标中的一个点 (i, height[i])。计算在下雨后能接多少雨水。

核心思路 ​

双指针的贪心思想：当前位置能接的水量取决于左侧最高和右侧最高中的较小值。双指针从两端向中间移动，每次处理较低的一侧。

代码实现 ​

javascript
/**
 * 接雨水 - 双指针解法（推荐）
 * @param {number[]} height
 * @return {number}
 */
function trap(height) {
  if (height.length < 3) return 0;

  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      // 处理左侧
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      // 处理右侧
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }

  return water;
}

/**
 * 接雨水 - 动态规划解法
 * 预计算左右两边的最大高度
 */
function trapDP(height) {
  const n = height.length;
  if (n < 3) return 0;

  // leftMax[i] = height[0...i] 的最大值
  const leftMax = new Array(n);
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  }

  // rightMax[i] = height[i...n-1] 的最大值
  const rightMax = new Array(n);
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  }

  // 计算每个位置能接的水量
  let water = 0;
  for (let i = 0; i < n; i++) {
    water += Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return water;
}

/**
 * 接雨水 - 单调栈解法
 * 维护递减栈，遇到比栈顶高的元素时计算
 */
function trapStack(height) {
  const stack = []; // 存储索引，对应的高度递减
  let water = 0;

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const mid = stack.pop();
      if (stack.length === 0) break;

      const left = stack[stack.length - 1];
      const h = Math.min(height[left], height[i]) - height[mid];
      const w = i - left - 1;
      water += h * w;
    }
    stack.push(i);
  }

  return water;
}

图解原理 ​

柱状图: [0,1,0,2,1,0,1,3,2,1,2,1]

可视化:
      █
  █~█~█~
█~█~█~█~█~█~
██████████

(~ 表示雨水的位置)

关键理解:
- 每个位置能盛的水 = min(左侧最高, 右侧最高) - 当前高度
- 双指针: 每次处理较低的一侧，因为较低一侧的接水量已确定

示例调用 ​

javascript
// 基础示例
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6

// 边界条件：少于3个柱子
console.log(trap([1, 2])); // 0
console.log(trap([1])); // 0
console.log(trap([])); // 0

// 边界条件：递增
console.log(trap([1, 2, 3, 4])); // 0

// 边界条件：递减
console.log(trap([4, 3, 2, 1])); // 0

// 边界条件：中间低两边高
console.log(trap([4, 2, 0, 3, 2, 5])); // 9
// 可视化:
//     █
//   █ █ █
// █ ~ █ ~ █
// █ ~ █ ~ █

// 边界条件：包含0
console.log(trap([0, 0, 3, 0, 0, 1])); // 3

// 边界条件：连续雨水
console.log(trap([3, 0, 2, 0, 4])); // 7

// 验证三种解法结果一致
const h = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log(trap(h));           // 6
console.log(trapDP(h));         // 6
console.log(trapStack(h));      // 6

复杂度分析 ​

解法时间复杂度空间复杂度特点
双指针O(n)O(1)最优，推荐
动态规划O(n)O(n)直观易懂
单调栈O(n)O(n)适合找凹陷

7. 搜索旋转排序数组 ​

LeetCode: 33. 搜索旋转排序数组 | 难度: 中等

题目描述 ​

升序数组在某个点进行了旋转（如 [0,1,2,4,5,6,7] 变为 [4,5,6,7,0,1,2]）。给定目标值，若存在返回索引，否则返回 -1。

核心思路 ​

二分查找：每次至少有一半是有序的，判断 target 在哪一半。

代码实现 ​

javascript
/**
 * 搜索旋转排序数组
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    
    if (nums[mid] === target) return mid;

    // 判断哪一半是有序的
    if (nums[left] <= nums[mid]) {
      // 左半部分有序
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 右半部分有序
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

示例调用 ​

javascript
// 基础示例
console.log(search([4, 5, 6, 7, 0, 1, 2], 0)); // 4

// 目标在左半部分
console.log(search([4, 5, 6, 7, 0, 1, 2], 5)); // 1

// 目标不存在
console.log(search([4, 5, 6, 7, 0, 1, 2], 3)); // -1

// 边界条件：单元素
console.log(search([1], 1)); // 0
console.log(search([1], 0)); // -1

// 边界条件：未旋转
console.log(search([1, 2, 3, 4, 5], 3)); // 2

// 边界条件：两个元素
console.log(search([3, 1], 1)); // 1

复杂度分析 ​

  • 时间: O(log n)
  • 空间: O(1)

8. 最小覆盖子串 ​

LeetCode: 76. 最小覆盖子串 | 难度: 困难

可视化演示：点击查看算法动画

题目描述 ​

给定字符串 s 和 t，返回 s 中涵盖 t 所有字符的最小子串。

代码实现 ​

javascript
/**
 * 最小覆盖子串
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);

  let left = 0, minLen = Infinity, start = 0;
  let required = need.size, formed = 0;
  const window = new Map();

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    window.set(c, (window.get(c) || 0) + 1);

    if (need.has(c) && window.get(c) === need.get(c)) {
      formed++;
    }

    // 收缩窗口
    while (formed === required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        start = left;
      }

      const d = s[left];
      window.set(d, window.get(d) - 1);
      if (need.has(d) && window.get(d) < need.get(d)) {
        formed--;
      }
      left++;
    }
  }

  return minLen === Infinity ? '' : s.substring(start, start + minLen);
}

示例调用 ​

javascript
// 基础示例
console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"

// 边界条件：t 包含重复字符
console.log(minWindow("aa", "aa")); // "aa"

// 边界条件：不存在
console.log(minWindow("a", "aa")); // ""

// 边界条件：s 等于 t
console.log(minWindow("abc", "abc")); // "abc"

复杂度分析 ​

  • 时间: O(n)
  • 空间: O(m)，m 为字符集大小

9. 岛屿数量 ​

LeetCode: 200. 岛屿数量 | 难度: 中等

可视化演示：点击查看算法动画

题目描述 ​

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿数量。

代码实现 ​

javascript
/**
 * 岛屿数量 - DFS
 * @param {character[][]} grid
 * @return {number}
 */
function numIslands(grid) {
  if (!grid.length) return 0;
  
  let count = 0;

  function dfs(i, j) {
    // 边界检查
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
    if (grid[i][j] !== '1') return;

    grid[i][j] = '0'; // 标记已访问
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  }

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);
      }
    }
  }

  return count;
}

示例调用 ​

javascript
// 基础示例
const grid1 = [
  ['1', '1', '1', '1', '0'],
  ['1', '1', '0', '1', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '0', '0', '0']
];
console.log(numIslands(grid1)); // 1

// 多个岛屿
const grid2 = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1']
];
console.log(numIslands(grid2)); // 3

// 边界条件：空网格
console.log(numIslands([])); // 0

// 边界条件：全是水
console.log(numIslands([['0', '0'], ['0', '0']])); // 0

// 边界条件：全是陆地
console.log(numIslands([['1', '1'], ['1', '1']])); // 1

复杂度分析 ​

  • 时间: O(m × n)
  • 空间: O(m × n) 最坏情况递归栈

💡 数组/字符串技巧总结 ​

技巧适用场景时间复杂度
哈希表查找配对、去重O(n)
双指针有序数组、回文O(n)
滑动窗口连续子串/子数组O(n)
二分查找有序数组搜索O(log n)
Kadane算法最大子数组和O(n)

前端面试知识库

Copyright © 2026