类别

问题名称

题目描述（一句话）

核心思路（一句话）

基础操作

1. 两数之和 (Two Sum)

在数组中找到两数，使它们的和等于目标值。

使用哈希表存储遍历过的值及其索引，检查目标值 – 当前值是否在表中。

2. 求最大/最小值

找出数组中的最大值和最小值。

遍历或分治法。分治即比较左右两半的最大最小值。

3. 求最大和次大值

找出数组中的最大值和次大值。

分治法。分别找出左右两半的最大次大值，再合并比较。

4. 出现次数超一半

找出在数组中出现次数超过一半的元素（主元素）。

摩尔投票法。不同元素相互抵消，最后剩下的候选者可能就是主元素。

排序与搜索

5. 合并区间

将重叠或相邻的区间合并。

按区间起点排序后，依次判断相邻区间是否能合并。

6. 数组第K大元素

找出数组中第K大的元素。

使用快速选择算法，基于快速排序的划分思想。

7. 搜索旋转排序数组

在一个可能在某点旋转过的有序数组中搜索目标值。

修改二分查找。通过比较中点与端点值，判断哪部分有序，并判断目标值位于哪部分。

双指针技巧

8. 三数之和

找出所有不重复的三元组，使它们的和为0。

先排序，固定一个数，对后续数组用双指针寻找两数之和。

9. 盛最多水的容器

用数组索引作为宽度，值作为高度，求最大矩形面积。

对撞指针。左右指针向中间移动，每次移动高度较小的指针，更新最大面积。

10. 删除排序数组重复项

原地删除排序数组中的重复元素，返回新长度。

快慢指针。慢指针指向已去重部分的末尾，快指针遍历，遇到不同元素则放入慢指针后。

滑动窗口

11. 最长无重复子串

找到字符串中最长的不包含重复字符的子串。

滑动窗口。用双指针表明窗口，用集合记录窗口内字符，移动右指针扩大窗口，遇重复则收缩左指针。

12. 滑动窗口最大值

给定数组和窗口大小，找出所有滑动窗口中的最大值。

使用单调双端队列维护窗口内可能成为最大值的索引。

动态规划

13. 最大子数组和

找出和最大的连续子数组。

动态规划。dp[i]表明以i结尾的最大和，dp[i] = max(nums[i], dp[i-1] + nums[i])。

14. 最长递增子序列

找到最长严格递增的子序列（不要求连续）。

动态规划。dp[i]表明以nums[i]结尾的LIS长度。或用贪心+二分维护最小尾部数组。

15. 编辑距离

计算将单词A转换成单词B所需的最少操作次数（增、删、替）。

动态规划。dp[i][j]表明A前i个字符转成B前j个字符的编辑距离，分情况讨论。

16. 打家劫舍

不能偷窃相邻的房屋，求能偷窃到的最高金额。

动态规划。dp[i] = max(dp[i-1], dp[i-2] + nums[i])，表明当前偷或不偷的最大收益。

矩阵与多维

17. 旋转图像

将 n × n 的矩阵顺时针旋转90度。

先沿主对角线翻转，再每一行反转；或分层处理四边元素交换。

18. 矩阵中的路径

判断字符矩阵中是否存在某条路径字符串。

回溯法。从每个点开始DFS，匹配字符串，失败则回溯，注意标记已访问。

19. 岛屿数量

计算由'1'（陆地）和'0'（水）组成的网格中岛屿的数量。

DFS/BFS。遍历网格，遇到未访问的'1'，则进行深度/广度优先搜索，标记整个岛屿。

特殊技巧

20. 下一个排列

将数组重新排列成字典序中下一个更大的排列。

1. 从右找第一个较小数a[i]。2. 从右找第一个大于a[i]的数a[j]并交换。3. 反转a[i]之后的序列。