数组核心操作与算法优化实战指南-开发者社区

1. 数组基础与核心操作解析

"代码随想录"算法训练营第二天的数组专题，聚焦数组这一基础数据结构的高效操作。作为算法入门的关键环节，数组操作看似简单却暗藏玄机。我在实际刷题中发现，90%的数组问题都可以转化为以下几种核心操作：

1.1 双指针法的三种经典形态

快慢指针处理数组元素移动时，需要特别注意指针移动的边界条件。以LeetCode 27题为例，移除指定元素的标准解法是：

def removeElement(nums, val): slow = 0 for fast in range(len(nums)): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 return slow

这里容易犯的错误是：

忘记检查fast指针越界
slow指针更新时机错误
返回值理解错误（应返回新长度）

实战经验：双指针移动时，建议先在纸上画出指针移动轨迹，特别是处理环形数组时，需要额外考虑模运算。

1.2 滑动窗口的两种实现范式

固定窗口大小的问题相对简单，但可变窗口需要掌握窗口收缩的触发条件。以最小覆盖子串为例：

def minWindow(s, t): need = collections.defaultdict(int) for c in t: need[c] += 1 left = valid = 0 res = "" for right in range(len(s)): # 窗口扩展逻辑 if s[right] in need: need[s[right]] -= 1 if need[s[right]] >= 0: valid += 1 # 窗口收缩条件 while valid == len(t): # 更新结果 if not res or right-left+1 < len(res): res = s[left:right+1] # 左指针移动 if s[left] in need: need[s[left]] += 1 if need[s[left]] > 0: valid -= 1 left += 1 return res

常见陷阱包括：

哈希表更新与valid计数不同步
结果更新时机不当
边界条件处理不严谨

2. 二维数组的特殊处理技巧

2.1 螺旋矩阵的层级遍历法

生成n×n螺旋矩阵时，采用分层填充策略可以避免复杂的坐标计算：

def generateMatrix(n): matrix = [[0]*n for _ in range(n)] left, right, top, bottom = 0, n-1, 0, n-1 num = 1 while left <= right and top <= bottom: # 从左到右 for i in range(left, right+1): matrix[top][i] = num num += 1 top += 1 # 从上到下 for i in range(top, bottom+1): matrix[i][right] = num num += 1 right -= 1 # 从右到左 for i in range(right, left-1, -1): matrix[bottom][i] = num num += 1 bottom -= 1 # 从下到上 for i in range(bottom, top-1, -1): matrix[i][left] = num num += 1 left += 1 return matrix

调试这类问题时：

使用小规模矩阵（如3×3）手动模拟
检查边界是否重复处理
注意奇数阶矩阵的中心点

2.2 对角线遍历的坐标映射

对于m×n矩阵的对角线遍历，关键在于发现行列索引之和的规律：

def findDiagonalOrder(matrix): if not matrix: return [] m, n = len(matrix), len(matrix[0]) result = [] 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: result.append(matrix[i][j]) i -= 1 j += 1 else: j = min(s, n-1) i = s - j while j >= 0 and i < m: result.append(matrix[i][j]) i += 1 j -= 1 return result

易错点包括：

方向切换条件判断错误
索引越界处理不当
空矩阵特殊情况遗漏

3. 数组排序的进阶应用

3.1 三路快排的partition优化

颜色分类问题（LeetCode 75）是理解三指针分区的绝佳案例：

def sortColors(nums): p0 = curr = 0 p2 = len(nums) - 1 while curr <= p2: if nums[curr] == 0: nums[p0], nums[curr] = nums[curr], nums[p0] p0 += 1 curr += 1 elif nums[curr] == 2: nums[curr], nums[p2] = nums[p2], nums[curr] p2 -= 1 else: curr += 1

关键细节：

curr与p2相遇时仍需处理
交换2时curr不前进（因为换来的可能是0）
终止条件的等号不能省略

3.2 逆序对问题的归并解法

在归并排序过程中统计逆序对，需要理解分治思想：

def reversePairs(nums): def merge_sort(l, r): if l >= r: return 0 mid = (l + r) // 2 count = merge_sort(l, mid) + merge_sort(mid+1, r) # 统计逆序对 j = mid + 1 for i in range(l, mid+1): while j <= r and nums[i] > 2 * nums[j]: j += 1 count += j - (mid + 1) # 合并有序数组 nums[l:r+1] = sorted(nums[l:r+1]) return count return merge_sort(0, len(nums)-1)

注意事项：