1. 数组专题概述：为什么hot100从数组开始？

数组作为计算机科学中最基础的数据结构之一，是算法面试中最高频的考察点。在各大公司的技术面试中，数组类题目占比超过30%，而hot100（LeetCode热门100题）中将数组作为首个专题，正是因为其兼具基础性和延展性的双重特点。

我刷过的近千道算法题中，数组问题往往具有以下特征：内存连续存储带来的高效随机访问（O(1)时间复杂度）、固定容量导致的边界处理难题、以及元素操作中隐藏的各类陷阱。这些特性使得看似简单的数组题能考察候选人的基础编码能力、边界条件处理意识和算法优化思维。

2. 核心解题框架与思维模型

2.1 双指针法的三种经典变体

双指针是数组问题中最常用的技巧，根据指针移动方式可分为：

1. 同向快慢指针（解决原地修改问题）

# 删除有序数组重复项 slow = 0 for fast in range(len(nums)): if nums[fast] != nums[slow]: slow += 1 nums[slow] = nums[fast]

2. 相向对撞指针（适用于排序数组）

# 两数之和II left, right = 0, len(nums)-1 while left < right: sum = nums[left] + nums[right] if sum == target: return [left+1, right+1] elif sum < target: left += 1 else: right -= 1

3. 分离指针（多数组处理）

# 合并两个有序数组 p1, p2 = m-1, n-1 for p in range(m+n-1, -1, -1): if p2 < 0: break if p1 >= 0 and nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1

关键经验：快慢指针的slow索引永远指向有效区间的末尾，这个认知能避免90%的off-by-one错误

2.2 前缀和与差分数组的魔法

前缀和技巧将O(n)的区间查询优化为O(1)，特别适合处理「区间和」类问题。差分数组则是前缀和的逆运算，擅长处理「区间增量」操作。

典型应用场景对比：

# 前缀和示例：区域和检索 class NumArray: def __init__(self, nums): self.prefix = [0] * (len(nums)+1) for i in range(len(nums)): self.prefix[i+1] = self.prefix[i] + nums[i] # 差分数组示例：航班预订统计 def corpFlightBookings(bookings, n): diff = [0] * (n+2) for start, end, seats in bookings: diff[start] += seats diff[end+1] -= seats return [diff[i]+=diff[i-1] for i in range(1,n+1)]

3. 高频题型深度剖析

3.1 旋转排序数组问题模板

旋转数组是面试官最爱的题型之一，其核心在于发现局部有序的特性。解题模板如下：

1. 确定旋转点（153.寻找旋转排序数组中的最小值）

left, right = 0, len(nums)-1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]

2. 在旋转数组中搜索（33.搜索旋转排序数组）

while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # 左半部分有序 if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # 右半部分有序 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1

易错点：边界条件处理需要特别注意等号情况，建议用具体测试用例验证

3.2 二维矩阵的四种遍历技巧

1. 螺旋遍历（54.螺旋矩阵）

def spiralOrder(matrix): res = [] while matrix: res += matrix.pop(0) matrix = list(zip(*matrix))[::-1] return res

2. 对角线遍历（498.对角线遍历）

m, n = len(mat), len(mat[0]) for s in range(m+n-1): if s % 2 == 0: i = min(s, m-1) j = s - i while i >= 0 and j < n: res.append(mat[i][j]) i -= 1 j += 1 else: j = min(s, n-1) i = s - j while j >= 0 and i < m: res.append(mat[i][j]) i += 1 j -= 1

3. 旋转图像（48.旋转图像）

# 先转置再镜像 n = len(matrix) for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] for row in matrix: row.reverse()

4. 矩阵前缀和（304.二维区域和检索）

class NumMatrix: def __init__(self, matrix): m, n = len(matrix), len(matrix[0]) self.prefix = [[0]*(n+1) for _ in range(m+1)] for i in range(m): for j in range(n): self.prefix[i+1][j+1] = matrix[i][j] + self.prefix[i][j+1] + self.prefix[i+1][j] - self.prefix[i][j]

4. 进阶技巧与优化策略

4.1 单调栈的巧妙应用

单调栈特别适合解决「下一个更大元素」类问题，其核心在于维护栈内元素的单调性：

# 739.每日温度 res = [0] * len(temperatures) stack = [] for i in range(len(temperatures)): while stack and temperatures[i] > temperatures[stack[-1]]: prev = stack.pop() res[prev] = i - prev stack.append(i)

变形应用——84.柱状图中最大的矩形：

heights.append(0) # 哨兵节点 stack = [-1] max_area = 0 for i in range(len(heights)): while heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i)

4.2 荷兰国旗问题与三向切分

快速排序中的partition操作进阶版，用于处理多类元素分组：

# 75.颜色分类 low, mid, high = 0, 0, len(nums)-1 while mid <= high: if nums[mid] == 0: nums[low], nums[mid] = nums[mid], nums[low] low += 1 mid += 1 elif nums[mid] == 1: mid += 1 else: nums[mid], nums[high] = nums[high], nums[mid] high -= 1

5. 实战问题排查与性能优化

5.1 边界条件处理大全

数组问题中最常见的三类越界错误：

1. 循环终止条件错误（是否包含等于）
2. 空数组/单元素数组特例
3. 整数溢出（特别是计算中间值时）

防御性编程技巧：在访问nums[mid]前先检查mid是否合法；对于可能为空的输入，在函数开头添加if not nums: return []

5.2 空间换时间的取舍艺术

当面试官要求优化时，考虑以下策略：

1. 原地修改 vs 额外空间：
   • 删除重复项：快慢指针O(1)空间
   • 合并有序数组：从后向前填充避免元素覆盖
2. 预处理策略：
   • 前缀和数组：适合多次查询
   • 哈希表缓存：适合两数之和类问题

# 优化版的两数之和 def twoSum(nums, target): num_map = {} for i, num in enumerate(nums): complement = target - num if complement in num_map: return [num_map[complement], i] num_map[num] = i

在刷hot100数组专题时，我最大的体会是：看似简单的数组题往往暗藏杀机。比如「盛最多水的容器」需要洞察高度与宽度的制约关系，「接雨水」需要理解动态规划与双指针的不同视角。建议每道题至少用两种方法实现，比较不同解法的时空复杂度，这样才能在面试中游刃有余。