数组算法题分类解析

1. 双指针

类型特点：通常用于处理有序数组或需要原地修改的问题。通过两个指针（同向或相向）协作，将 O(n²) 的暴力解法优化至 O(n)。

难度	题目	题号	核心思路简介
简单	删除有序数组中的重复项	26	快慢指针，慢指针维护无重复区间
简单	移除元素	27	快慢指针，将与目标值相等的元素移除
简单	合并两个有序数组	88	从后往前双指针，避免覆盖原数组元素
中等	盛最多水的容器	11	左右指针向中间移动，每次移动高度较小的指针
中等	三数之和	15	排序后，固定一个数，再用双指针寻找另外两个数

2. 滑动窗口

类型特点：用于寻找满足特定条件的连续子数组，如“最长子数组”、“最小子数组”。

难度	题目	题号	核心思路简介
中等	长度最小的子数组	209	窗口和小于目标时右移右指针，大于等于时尝试左移左指针
中等	无重复字符的最长子串	3	用哈希记录窗口内字符，右指针移动时发现重复则左指针收缩

3. 前缀和 & 哈希表优化

类型特点：频繁需要计算子数组的和或统计满足特定和条件的子数组个数。

难度	题目	题号	核心思路简介
中等	和为 K 的子数组	560	计算前缀和，用哈希表存储前缀和出现的次数，查找 当前前缀和 - k 的次数
中等	除自身以外数组的乘积	238	用前缀积和后缀积（或两次遍历），当前位置结果 = 左边乘积 * 右边乘积

4. 二分查找

类型特点：数组通常是有序的，或者题目要求时间复杂度为 O(log n)。

难度	题目	题号	核心思路简介
简单	搜索插入位置	35	标准二分查找，寻找第一个大于等于目标值的下标
中等	在排序数组中查找元素的第一个和最后一个位置	34	两次二分查找，分别寻找左边界和右边界
中等	搜索旋转排序数组	33	先判断哪一部分有序，再根据目标值决定搜索哪一半
困难	寻找两个正序数组的中位数	4	在两个有序数组中用二分法找到一条分割线，使左右两部分元素个数相等且满足大小关系

5. 贪心算法

类型特点：求最值问题，且局部最优解可以推导出全局最优解。

难度	题目	题号	核心思路简介
中等	跳跃游戏	55	维护当前能到达的最远距离，判断是否能走到终点
中等	加油站	134	如果总油量大于等于总消耗，则从某个点出发一定能成功。从起始点累加剩余油量，若小于0则更新起始点

6. 动态规划

类型特点：求最值、方案数或可行性问题，且问题可以被分解为重叠的子问题。

难度	题目	题号	核心思路简介
简单	爬楼梯	70	dp[i] = dp[i-1] + dp[i-2]
中等	最大子数组和	53	dp[i] 表示以 i 结尾的连续子数组最大和，状态转移为 max(dp[i-1]+nums[i], nums[i])
中等	不同路径	62	二维DP，dp[i][j] = dp[i-1][j] + dp[i][j-1]
中等	打家劫舍	198	dp[i] 表示偷到第 i 家时的最大金额，考虑偷或不偷当前这家

7. 矩阵操作

类型特点：将一维数组的概念扩展到二维矩阵，考察坐标变换和模拟能力。

难度	题目	题号	核心思路简介
中等	螺旋矩阵	54	按层（上、右、下、左）模拟遍历，注意边界条件
中等	旋转图像	48	先按对角线翻转，再按行翻转
中等	矩阵置零	73	用第一行和第一列作为标记位，原地修改

8. 进阶技巧

类型特点：通常为困难题，需要用到特殊的数据结构或算法思想，是对前面基础知识的综合运用。

难度	题目	题号	核心思路简介
困难	接雨水	42	方法多样：动态规划（找左右最大值）、双指针、单调栈
困难	数组中的逆序对	剑指 Offer 51	归并排序的分治思想，在合并过程中统计
困难	寻找重复数	287	将数组视为链表，用快慢指针找环入口；或用二分法按值搜索

刷题建议

1. 由浅入深：先从“双指针”和“二分查找”的简单题入手，建立信心。
2. 掌握模板：重点攻克“滑动窗口”和“前缀和”，这两类题的代码框架非常固定，性价比很高。
3. 思维提升：带着状态转移方程的思想去练习“动态规划”，这是面试中的分水岭题型。
4. 查漏补缺：当遇到难题时，可以参考题解区的“官方题解”或高赞回答，学习最优解法的思路。