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、双指针、排序和边界验证。
配套刷题：
