掌握数组算法，就掌握了算法面试的半壁江山

数组是算法面试中最基础也最核心的数据结构，本文系统总结九大数组算法技巧，涵盖从基础到高阶的所有解题思路。每种技巧均配以LeetCode经典题目解析，助你彻底攻克数组类题目。

1. 排序：算法基石

核心思想：有序数组能极大简化问题复杂度

# 快速排序
def quicksort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

应用场景：

• 求最近元素（LeetCode 16. 最接近的三数之和）
• 找中位数（LeetCode 4. 寻找两个正序数组的中位数）
• 合并区间（LeetCode 56. 合并区间）

时间复杂度：O(n log n) 是大多数问题的起点

2. 双指针：高效遍历的利器

核心思想：用两个指针协同遍历，减少不必要的计算

类型一：同向双指针（滑动窗口）

# LeetCode 209. 长度最小的子数组
def minSubArrayLen(target, nums):
    left = total = 0
    min_len = float('inf')
    
    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            min_len = min(min_len, right-left+1)
            total -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

适用场景：

• 连续子数组问题
• 字符串匹配
• 去除重复元素（LeetCode 26. 删除有序数组中的重复项）

类型二：对向双指针

# LeetCode 11. 盛最多水的容器
def maxArea(height):
    left, right = 0, len(height)-1
    max_area = 0
    
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

适用场景：

• 两数之和（LeetCode 167. 两数之和 II）
• 回文串判断（LeetCode 125. 验证回文串）
• 三数之和（LeetCode 15. 三数之和）

3. 哈希映射：空间换时间的典范

核心思想：用O(1)时间实现元素查找

# LeetCode 1. 两数之和
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
    return []

应用场景：

• 元素存在性检查
• 频率统计（LeetCode 347. 前 K 个高频元素）
• 索引映射（LeetCode 205. 同构字符串）

时间复杂度：O(n) 空间复杂度：O(n)

4. 前缀和：区间问题的优化器

核心思想：预处理数组，实现O(1)区间求和

# LeetCode 560. 和为 K 的子数组
def subarraySum(nums, k):
    prefix_sum = {0: 1}
    current_sum = 0
    count = 0
    
    for num in nums:
        current_sum += num
        # 查找是否存在前缀和满足 current_sum - prefix = k
        count += prefix_sum.get(current_sum - k, 0)
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
    
    return count

应用场景：

• 区间求和（LeetCode 303. 区域和检索）
• 矩阵区域和（LeetCode 304. 二维区域和检索）
• 平均数限制（LeetCode 643. 子数组最大平均数 I）

5. 差分数组：区间更新的优化方案

核心思想：用增量表示变化，最后统一计算

# LeetCode 1109. 航班预订统计
def corpFlightBookings(bookings, n):
    diff = [0] * (n + 1)
    
    for first, last, seats in bookings:
        diff[first-1] += seats
        if last < n:
            diff[last] -= seats
    
    # 通过差分数组重建结果
    res = [0] * n
    res[0] = diff[0]
    for i in range(1, n):
        res[i] = res[i-1] + diff[i]
    
    return res

应用场景：

• 区间增减操作（LeetCode 370. 区间加法）
• 会议室预定问题
• 公交路线统计

6. 计数技巧：有限空间的优化

核心思想：当元素范围有限时，用数组代替哈希表

# LeetCode 242. 有效的字母异位词
def isAnagram(s, t):
    if len(s) != len(t): return False
    
    counter = [0] * 26
    
    for char in s:
        counter[ord(char) - ord('a')] += 1
    
    for char in t:
        index = ord(char) - ord('a')
        counter[index] -= 1
        if counter[index] < 0:
            return False
    
    return True

应用场景：

• 字符统计（LeetCode 387. 字符串中的第一个唯一字符）
• 投票统计（LeetCode 169. 多数元素）
• 有限范围整数处理（LeetCode 41. 缺失的第一个正数）

7. 摩尔投票法：空间O(1)的众数查找

核心思想：元素抵消策略找绝对众数

# LeetCode 169. 多数元素
def majorityElement(nums):
    count = 0
    candidate = None
    
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    
    return candidate

扩展应用：

• 泛化版本（LeetCode 229. 求众数 II）
• 数据流处理
• 大规模日志分析

8. 分治策略：化繁为简的利器

核心思想：分而治之，合并结果

# LeetCode 53. 最大子数组和（分治解法）
def maxSubArray(nums):
    def divide_conquer(left, right):
        if left == right:
            return nums[left]
        
        mid = (left + right) // 2
        
        # 分别求解左右子问题
        left_max = divide_conquer(left, mid)
        right_max = divide_conquer(mid+1, right)
        
        # 计算跨越中点的最大值
        left_sum = right_sum = float('-inf')
        total = 0
        for i in range(mid, left-1, -1):
            total += nums[i]
            left_sum = max(left_sum, total)
        
        total = 0
        for i in range(mid+1, right+1):
            total += nums[i]
            right_sum = max(right_sum, total)
        
        cross_max = left_sum + right_sum
        
        return max(left_max, right_max, cross_max)
    
    return divide_conquer(0, len(nums)-1)

应用场景：

• 归并排序
• 逆序对计算（LeetCode 493. 翻转对）
• 最大子数组问题
• 最近点对问题

9. 位运算：极致性能的秘诀

核心思想：利用位操作实现底层优化

# LeetCode 136. 只出现一次的数字
def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num  # 异或运算
    return result

高级技巧：

• 位掩码（LeetCode 78. 子集）
• 位计数（LeetCode 338. 比特位计数）
• 位压缩状态（LeetCode 187. 重复的DNA序列）

数组算法选择指南

问题特征	推荐方法	经典例题
有序数组查找	二分查找	34. 在排序数组中查找元素的第一个和最后一个位置
连续子数组问题	滑动窗口/前缀和	209. 长度最小的子数组
元素关系统计	哈希映射	1. 两数之和
区间更新查询	差分数组	370. 区间加法
绝对众数查找	摩尔投票法	169. 多数元素
大规模数据处理	分治策略	53. 最大子数组和（分治版）
有限范围元素处理	计数数组	41. 缺失的第一个正数
状态压缩优化	位运算	78. 子集

实战综合应用：LeetCode 238. 除自身以外数组的乘积

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    
    # 从左向右累积（存储左侧乘积）
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]
    
    # 从右向左累积（乘以右侧乘积）
    right_product = 1
    for i in range(n-1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]
    
    return result

技巧融合：

1. 左右双指针遍历
2. 前缀积思想
3. 空间复用优化（O(1)额外空间）

总结：数组算法核心思维

1. 空间权衡：哈希表 vs 计数数组 vs 原地操作
2. 时间优化：排序预处理 vs 双指针遍历 vs 前缀和预计算
3. 状态维护：滑动窗口的状态更新 vs 差分数组的增量记录
4. 分治思想：大问题拆解为独立子问题
5. 位级优化：利用位运算实现底层高效操作

高级技巧：当遇到复杂数组问题时，尝试组合使用多种技巧：

1. 排序 + 双指针（三数之和）
2. 前缀和 + 哈希表（和为K的子数组）
3. 差分数组 + 贪心（会议室安排）
4. 位运算 + 分治（大规模数据处理）

掌握这九大核心技巧，90%的数组类算法问题都将迎刃而解。最重要的是理解每种技巧的适用场景和底层原理，而非死记硬背解法。