2. 数组题常见解法怎么总结

数组题是测试岗手撕代码中最常见的题型。数组题看起来简单，但非常容易考察下标、边界、重复元素、空数组、原地修改和复杂度。很多测试同学写数组题时，思路能想到，但代码容易出现下标越界、漏处理空数组、循环条件写错。准备数组题的重点不是刷很多难题，而是总结常见解法套路。

数组题常用方法包括：暴力遍历、Map 辅助、双指针、排序、前缀和、原地交换。测试岗位常考的是基础到中等难度，最需要写熟的是：求最大最小值、数组去重、两数之和、移动零、合并数组、找重复数字、找缺失数字。

一、数组题先看什么

拿到数组题，不要急着写。先确认：

数组是否可能为空；
元素是否有重复；
是否有负数；
是否要求返回下标还是值；
是否允许修改原数组；
是否要求原地操作；
是否对时间复杂度有要求；
数组是否有序。

这些条件决定解法。

二、遍历法

最基础的方法是遍历数组。

例如求最大值：

def max_value(nums):
    if not nums:
        return None
    max_num = nums[0]
    for num in nums:
        if num > max_num:
            max_num = num
    return max_num

边界：空数组、单元素、全负数、重复最大值。

遍历法是很多题的基础，时间复杂度通常是 O(n)。

三、Map 辅助法

当题目涉及“查找是否出现过”“统计次数”“快速找补数”时，可以考虑 Map。

典型题：两数之和。

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

Map 用空间换时间，把双层循环优化成单层循环。

适合题型：

两数之和；
找重复元素；
统计数字频次；
找第一个重复值。

四、双指针法

双指针适合有序数组、原地修改、首尾夹逼。

例如反转数组：

def reverse_array(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

例如移动零：

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

双指针常考察边界和指针移动条件。

五、排序法

排序可以让问题变简单，比如找重复、找第 k 大、合并数组等。

但排序会改变顺序，复杂度通常 O(n log n)。如果题目要求保留原顺序，就不能直接排序。

例如判断是否存在重复：

def has_duplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

也可以用 Set 更简单。

六、前缀和法

前缀和适合区间和问题。

例如给定数组，快速求某个区间和。

def prefix_sum(nums):
    pre = [0]
    for num in nums:
        pre.append(pre[-1] + num)
    return pre

区间 [l, r] 的和是：

pre[r + 1] - pre[l]

测试岗不一定常考复杂前缀和，但理解思路有帮助。

七、数组去重怎么写

如果不要求原地，可以用 Set：

def unique(nums):
    return list(set(nums))

但 Set 不保证顺序。如果要保留顺序：

def unique_keep_order(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

面试时要先问是否要求保留顺序。

八、合并两个有序数组

可以用双指针：

def merge_sorted(a, b):
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

边界：一个数组为空、两个数组都有重复、长度不同。

九、数组题常见边界

数组题一定要主动补边界：

空数组；
单元素数组；
两个元素；
全部相同；
有负数；
有重复；
已排序；
逆序；
目标不存在；
大数据量。

测试岗面试主动补边界会加分。

十、面试回答模板

如果面试官问“数组题常见解法怎么总结”，可以这样回答：

数组题我会先确认是否为空、是否有序、是否允许修改原数组、是否有重复、返回下标还是值。常见解法包括遍历、Map 辅助、双指针、排序和前缀和。比如两数之和可以用 Map 保存已遍历元素，时间复杂度 O(n)；移动零和反转数组适合双指针；去重可以用 Set，但如果要保留顺序，需要额外维护结果列表；合并有序数组可以用两个指针。写完后我会用空数组、单元素、重复元素、负数和目标不存在这些边界验证。

十一、练习清单

求最大值；
求最小值；
两数之和；
数组去重；
移动零；
合并有序数组；
查找重复数字；
找缺失数字；
反转数组；
固定区间求和。

数组题是手撕代码基本功。重点不是背答案，而是掌握遍历、Map、双指针、排序和边界验证。

配套刷题：

手撕代码