数组算是我在力扣Hot 100这个题库里认真啃下来的第一个专题。刚开始真没当回事觉得数组不就是for循环加下标访问能难到哪里去直到有一次面试被一道“和为K的子数组”问得当场卡壳我才意识到数组题型远没有想象中简单。后来我把Hot 100里所有数组类题目集中刷了三遍又对着高频面试题把代码重写了无数次才慢慢摸出一套完整的数组题解法体系。这篇文章就是我整理出来的完整笔记从题型分类、通用套路到Java实现细节全部拆开讲清楚。这篇笔记的定位很明确一是给刚开始刷Hot 100、不知道从哪里下手的Java选手踩出一条路二是给刷过一遍但总是记不住套路、面试容易卡壳的同学做一次系统梳理。数组在Hot 100里出题密度非常高据统计大约有三分之一题目的核心解法都建立在数组上所以这块啃透了后面的链表、字符串、矩阵题会轻松很多。下面我直接上干货。1. 数组题在Hot 100中的分量与整体思路1.1 数组题型为什么会成为面试必考数组几乎是所有算法题的基础载体。面试官考察数组题本质上是在考察你三个东西对下标边界的敏感度、对空间复杂度的控制能力、以及对常见算法套路双指针、哈希、前缀和、滑动窗口的熟练程度。这三点恰恰是工程开发中最基础也最容易出bug的地方。举个很简单的例子很多人写for循环时习惯用for (int i 0; i nums.length; i)多一个等号数组就越界。这种低级错误在面试高压环境下特别容易犯而数组题天然就是用来检验这种基本功的。再说实际业务场景数组本身在Java开发里太常用了数据库查询结果集需要转数组、日志解析需要切片数组、统计报表需要对数组做聚合计算。面试官问数组题不只是考算法还在考察你写业务代码的底层功底。Hot 100里的数组题之所以经典是因为每道题都能映射到一类真实问题。1.2 先把数组题按“套路”分好类很多同学刷Hot 100容易陷入一个误区从头按题号一道一道刷。结果刷到第50题时前面30题的解法早就忘光了。我的做法是先做分类把数组题按照解法套路拆成几个大类一类一类地啃这样记忆才有锚点。以Hot 100的数组题为例我一般分成四类查找类典型代表是“两数之和”“三数之和”核心思路是哈希表辅助或者排序后双指针。子数组类典型代表是“最大子数组和”“和为K的子数组”核心思路是动态规划、前缀和、滑动窗口。区间类典型代表是“合并区间”核心思路是排序加贪心。原地操作类典型代表是“移动零”“除自身以外数组的乘积”核心思路是快慢指针、状态标记重点考察空间复杂度。这个分类不是死的比如“盛最多水的容器”既可以归为查找类也能归为双指针类但分类的目的只是帮你建立思路索引。当你拿到一道没见过的题时第一步就是判断它属于哪一类然后去套那一类对应的解法模板。这个思维方式比背题重要得多。1.3 我的专题刷题法不要按题号硬刷我个人的建议是不要直接用LeetCode的题号顺序刷Hot 100而是先按标签把所有数组题筛出来集中一段时间只刷数组题。我第一轮就是按题号硬刷刷到一半整个人都乱了今天做哈希明天做回溯知识体系压根建立不起来。第二轮我换成“专题刷题法”先花一天时间把数组题全部扫一遍把每道题对应的解法标签写在表格里然后按标签分组练习。比如今天只写双指针的题明天只写前缀和的题后天只写滑动窗口的题。这样做最大的好处是大脑能进入一种“模式识别”状态同一个套路连续练五六道题之后不用看题解也能顺手写出来。分类表格比想象中有用。我后来把表格打印出来贴在显示器旁边每天刷题前先看一眼面试前也靠它快速恢复记忆。这类整理工作看起来费时间但实际上比多刷十道题还值。2. 高频基础方法双指针、前缀和、哈希与滑动窗口2.1 双指针把O(n^2)暴力优化成O(n)的利器双指针在数组题里的地位就像弓箭在冷兵器时代一样简单但好用。核心思想是维护两个指向数组不同位置的指针根据条件移动其中一个或两个从而在一次遍历里完成原本需要嵌套循环才能完成的比较。以Hot 100里的“盛最多水的容器”为例题目是给一个高度数组找出两条线能容纳最多水的面积。暴力解法是两两组合求最大值时间复杂度O(n^2)数据量一大直接超时。双指针的解法是从数组两端开始每次移动高度较矮的那一侧指针因为面积取决于较矮的板子移动高板子只会让面积更小所以这个移动策略是正确且高效的。public int maxArea(int[] height) { int left 0, right height.length - 1; int max 0; while (left right) { int area Math.min(height[left], height[right]) * (right - left); max Math.max(max, area); if (height[left] height[right]) { left; } else { right--; } } return max; }这段代码里最核心的是那行if (height[left] height[right])每移动一次就排除掉一类不可能成为最优解的组合。这类题的关键是分析“移动哪个指针不会丢失最优解”想明白这一步双指针基本就掌握了。2.2 前缀和连续子数组求和的第一反应前缀和这个概念其实特别朴素用一个新数组保存原数组从开头到当前位置的累加和。为什么有用因为任意子数组[i, j]的和都可以用两个前缀和相减得到即preSum[j1] - preSum[i]。这样一来原本每次都要循环求和的区间块变成了O(1)的查表运算。我打一个不太严谨但很好懂的比方前缀和就像记账。你只需要记住每个月底的账户余额想知道某个月份的支出直接用下个月的余额减去上个月的余额就行不用再去翻每一天的消费记录。前缀和的典型应用场景是“子数组和等于某个目标值”“子数组和最大/最小”“区域查询累计值”。Hot 100里的“和为K的子数组”就是前缀和的经典题目但这里有个进阶技巧单纯用前缀和数组仍然需要双重循环遍历所有区间要真正优化到O(n)还得配合哈希表使用。关于这道题我在第三节会详细拆解。2.3 哈希表辅助用空间换时间的经典做法数组题里哈希表最常见的用途就是找“之前有没有出现过某个值”。暴力做法是每到一个数就往前扫描一遍哈希表做法是把每个已经见过的值存进Map遇到新数时用O(1)的时间去查Map空间开销从O(1)变成O(n)但时间从O(n^2)降到O(n)。Java里面HashMap的底层是数组加链表加红黑树它在算法题里几乎成为“两数之和”的标配解法。不过用哈希表有一个容易忽视的问题key存什么、value存什么。比如两数之和里存的是“数值到下标”的映射和为K的子数组里存的是“前缀和到出现次数”的映射。存错key或者存错value代码逻辑直接崩。我用哈希表时还有个经验尽量先写getOrDefault不要先判断containsKey再get后者不仅代码啰嗦还会比前者多做一次哈希操作性能略差。两数之和解法里我没法用getOrDefault因为要区分下标为0的情况但很多场景下getOrDefault一行就能搞定。2.4 滑动窗口处理“连续区间”问题的通用框架滑动窗口本质上也是双指针的一种但它的特点是两个指针只向前移动不回头维护的区间像一个窗口在数组上滑过。它适合解决“连续子数组/子串满足某种条件”的问题比如“长度最小的子数组”“无重复字符的最长子串”之类的变体。滑动窗口的框架可以总结成四步右指针不断右移扩大窗口每次更新窗口内状态判断窗口是否满足条件如果不满足或为了找最优解就移动左指针收缩窗口同时更新状态。模板背熟之后大部分滑动窗口题就是改改状态更新的代码。但滑动窗口有个天然限制窗口内的状态必须能通过“加减元素”快速更新。如果窗口收缩时状态很难维护那就得换思路。比如“和为K的子数组”这道题虽然也是连续子数组问题但因为数组里可能有负数滑动窗口的单调性被破坏不能简单套用必须走前缀和加哈希表的路线。所以别死记模板要理解模板的适用前提。3. hot100数组题实操拆解五道必刷题目3.1 两数之和HashMap如何替代双重循环两数之和几乎是所有人进入算法世界的入门题题目不用多说给定数组和一个目标值找出数组中两个数之和等于目标值的下标。暴力解法是双重循环遍历每一对组合时间复杂度O(n^2)。数据规模一大这种解法在面试官眼里基本就是不及格。优化思路是遍历数组时把已经访问过的数存进哈希表每次处理当前数nums[i]时直接查表看target - nums[i]是否出现过。如果出现过就找到了答案没出现过就把当前数和它的下标存入Map继续往后遍历。这样只用一次遍历时间O(n)空间O(n)。public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int need target - nums[i]; if (map.containsKey(need)) { return new int[]{map.get(need), i}; } map.put(nums[i], i); } return new int[]{-1, -1}; }这里有个细节先把target - nums[i]算出来放在变量里再查表不要直接在if条件里写map.containsKey(target - nums[i])虽然功能一样但后者会让调试时看不清到底存的是什么值代码整洁度也差一些。返回值固定用new int[]{}不要先声明一个数组再手动赋值后者多写两行还容易漏初始化。这道题我面试时被问过至少五次每次都会附带一个追问如果数组有序能不能不用哈希表答案是用双指针从两端向中间逼近空间复杂度可以降到O(1)。3.2 移动零快慢指针的现场教学移动零的题目描述非常朴素把数组里的所有0移动到末尾同时保持非零元素的相对顺序。难点在于题目的额外要求必须原地操作不能复制数组。很多人的第一反应是新建一个数组把非零元素放进去再把后面填0但这个做法空间复杂度是O(n)不满足要求。快慢指针在这里非常好用。慢指针指向下一个应该放置非零元素的位置快指针负责往前扫描找非零元素。每当快指针遇到非零元素就和慢指针指向的位置交换然后慢指针前进一位。这样一轮遍历结束后所有非零元素都被换到数组前面0自然被挤到末尾。public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { int tmp nums[slow]; nums[slow] nums[fast]; nums[fast] tmp; slow; } } }注意我写的是交换而不是“把非零元素赋值到前面再把原位置改成0”。交换的好处是操作逻辑简单也利于扩展到其他题目。有一个边界情况容易踩坑整个数组全是非零元素时快慢指针始终指向同一个位置交换相当于自己和自己换没问题但如果你用赋值加置0的写法就得多加一个判断否则会把没遍历到的数据覆盖掉。平时刷题我喜欢把这类“看起来没坑”的小题也认真写一遍因为正式面试时手写代码很容易暴露这些细节。3.3 最大子数组和动态规划在数组题里的代表作最大子数组和要求找出数组中的一个连续子数组使得它们的和最大。比如[-2,1,-3,4,-1,2,1,-5,4]的最大子数组是[4,-1,2,1]和为6。这个看似简单的问题暴力解法要枚举所有起点和终点O(n^2)数据规模一大就废了。正确解法用动态规划思想关键定义是pre表示以当前元素结尾的最大子数组和。状态转移方程特别简洁pre Math.max(pre x, x)。意思是要么把当前元素接在前面的子数组后面要么从当前元素重新开始。为什么需要这个选择因为如果前面的累加和是负数接上当前元素只会拖累结果不如从当前元素重新开头。public int maxSubArray(int[] nums) { int pre 0; int max nums[0]; for (int x : nums) { pre Math.max(pre x, x); max Math.max(max, pre); } return max; }这里有一个经典的初始化坑max的初始值不能设成0因为如果数组里全是负数正确答案会是一个负数。用nums[0]初始化就不会出问题。我见过很多人在这道题上栽跟头不是状态转移方程不会写而是初始化不严谨。另外这个状态转移其实只用了一个变量不需要额外开数组属于典型的滚动变量优化。3.4 合并区间排序后贪心合并的关键合并区间是一类很实际的题目可以理解为把多个时间区间合并成不重叠的完整区间。比如[[1,3],[2,6],[8,10],[15,18]]因为[1,3]和[2,6]有重叠合并成[1,6]最终结果是[[1,6],[8,10],[15,18]]。解法的第一步几乎没有任何悬念按区间左端点排序。排序之后重叠的区间在位置上一定是相邻的这为后续的合并提供了极大便利。然后遍历每个区间维护一个当前合并区间。如果新区间的左端点大于当前合并区间的右端点说明两者不相交把当前合并区间加入结果开始一个新的合并区间否则说明有重叠更新当前合并区间的右端点为较大值。public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) - a[0] - b[0]); Listint[] res new ArrayList(); for (int[] cur : intervals) { if (res.isEmpty() || cur[0] res.get(res.size() - 1)[1]) { res.add(cur); } else { int[] last res.get(res.size() - 1); last[1] Math.max(last[1], cur[1]); } } return res.toArray(new int[res.size()][]); }这段代码有个很tricky的地方当没有重叠时res.add(cur)不是复制区间而是直接存了原数组的引用后续修改cur会不会影响结果这里不会因为进入不重叠分支的cur在下一轮迭代里会被指向新的区间对象之前的cur不会再被修改。但如果觉得这样不够保险可以new int[]{cur[0], cur[1]}后再add代码长度差不多可读性更好。另外注意排序时用(a, b) - a[0] - b[0]可能int溢出虽然区间端点一般不会出现极端值但严谨一点可以写成Integer.compare(a[0], b[0])。3.5 和为K的子数组前缀和与哈希表的组合应用这道题是我印象最深的一道也是我开头说的面试翻车现场。题目是求数组中和为k的连续子数组的个数。比如[1,2,3]且k3答案是2因为[1,2]和[3]都满足。第一反应很容易想到滑动窗口但这道题有个陷阱数组元素可能包含负数窗口扩大时和不一定变大缩小时也不一定变小滑动窗口的两个指针没法保持单调移动所以此路不通。正确解法是前缀和加哈希表。思路是这样的遍历数组时维护一个累计和sum对于当前位置i我们想知道有多少个以i结尾的子数组和为k。子数组的区间是[j, i]对应的和为sum(i) - sum(j-1)。想让它等于k就要知道前面有多少个位置的前缀和等于sum - k。所以用一个Map记录每个前缀和出现的次数每次累加答案。public int subarraySum(int[] nums, int k) { MapInteger, Integer prefixCount new HashMap(); prefixCount.put(0, 1); int sum 0, count 0; for (int num : nums) { sum num; count prefixCount.getOrDefault(sum - k, 0); prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) 1); } return count; }初始化时为什么要put(0, 1)因为如果某个位置的前缀和恰好等于k说明从数组开头到该位置的子数组本身就是答案计算时sum - k 0需要能从Map里查到0出现过一次。这个初始值漏掉的话这类子数组就被漏算了。我第一遍刷这道题时就是漏了这一步答案总是差几个数排查了很久才发现。这种细节不踩一次坑光看题解是真的很难注意到。4. Java数组的工程细节与高频踩坑4.1 数组与集合互转的几个大坑算法题里经常要把数组转成List方便操作或者把List转回数组作为返回值。这中间有太多隐藏的坑我一个个说。第一个坑Arrays.asList返回的List是定长的。很多人以为asList出来的集合和new ArrayList一样可以随便add和remove但实际上它返回的是Arrays内部的一个固定长度视图底层还是原数组调用add会直接抛UnsupportedOperationException。如果后续代码里有增删操作一定要这样写new ArrayList(Arrays.asList(arr))。第二个坑基本类型数组不能直接用asList。比如int[]在泛型推断时int[]被当成一个整体对象asList返回的Listint[]里只有一个元素长度是1而不是数组长度。想要把int[]转成ListInteger常见做法是用Java 8 StreamArrays.stream(nums).boxed().collect(Collectors.toList())。这个方法用起来还行但要注意boxed()不可省否则流里的类型还是IntStream。第三个坑List转数组时toArray()无参版本返回的是Object[]并不是Integer[]。想要正确得到对应类型数组需要传入一个类型正确的空数组list.toArray(new Integer[0])。在算法题里二维数组的构造也常用toArray(new int[res.size()][])这种方式比较高效。4.2 Arrays工具类排序、二分、拷贝的正确用法Java的Arrays工具类在算法题里使用频率极高但很多人只停留在Arrays.sort这一招上。实际上数组拷贝、二分查找、填充操作在特定场景下能极大简化代码。Arrays.sort既能直接排序基本类型数组也能通过传入比较器排序对象数组。二维数组按某一列排序是算法题高频操作写法是Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]))。注意Integer.compare比直接相减更安全避免溢出。Arrays.binarySearch是二分查找的现成实现但返回值设计得很反直觉找到了返回下标没找到返回-(插入点) - 1。很多人用的时候忘记处理负数直接拿来当下标用结果数组越界。我一般只在数组已排序且能确定元素必然存在时才会用binarySearch否则还是老老实实自己写二分。Arrays.copyOf和System.arraycopy是数组扩容和拷贝的底层实现ArrayList的扩容就是靠System.arraycopy完成的。刷题时如果遇到需要“取数组前n个元素”的场景Arrays.copyOfRange(nums, start, end)比手写循环清爽很多。4.3 笔试场景下的输入输出与初始化问题在真正的笔试环境中很多题目给的输入不是函数参数而是标准输入流里的字符串。这时候考验的就是字符串解析和数组初始化的基本功了。题目输入通常是[1,2,3,4]需要自己把中括号去掉按逗号split然后逐个parse成int。我用得比较多的一种解析方式是先用replace把中括号等无关字符处理掉再以逗号分割循环赋值。比如String[] parts input.replace([, ).replace(], ).split(,)然后int[] arr new int[parts.length]循环里Integer.parseInt(parts[i].trim())。这道工序看起来琐碎但在笔试里至少能占3到5分钟提前写好模板能节省大量时间。初始化方面有个很常见的bug定义最大最小值时一定要初始化为Integer.MIN_VALUE和Integer.MAX_VALUE不能随手写成0。计算最大子数组和时max初始化成0会漏掉全负数的情况计算最小差值时min初始化成0会导致结果永远是0。我建议在本地编辑器里把这几种初始化场景存成代码片段写的时候直接调。还有一个初学阶段特别容易忽略的问题引用类型数组的默认值是null。比如String[] strArr new String[5]里面全是null直接调用strArr[0].length()会抛NullPointerException。我刚实习的时候写业务代码就犯过这个错后来养成了一个习惯声明完数组后先想想里面存的是基本类型还是引用类型如果是引用类型检查是否每个元素都初始化了。4.4 把“代码整洁度”练进肌肉记忆面试手写代码和平时在IDE里写代码是完全不同的体验。没有自动补全没有编译提示甚至没有语法高亮代码整洁度直接影响面试官对你的印象分。我在刷题时有几个固定的整洁度要求大括号不省略函数统一用public修饰变量名用有含义的词而不是a、b、tmp乱写每个方法控制在30行以内。还有一个容易被忽视的细节边界条件统一放在方法开头处理。比如数组为空或者长度小于2时应该怎么做先想清楚再写主逻辑。我在两数之和的解法里就有一个冗余写法return new int[]{-1, -1}这就是为了应对“没找到答案”的情况。虽然按题意不会发生但写上之后代码是完整自洽的。面试官看到这种防御式写法好感度会明显上升。5. 常见问题与排查技巧实录5.1 数组题最容易翻车的6个运行时报错数组题出错几乎都集中在几个固定模式上我把最常见的6类错误整理成一张速查表没事翻一翻能省很多调试时间。错误类型典型触发场景解决思路ArrayIndexOutOfBoundsException循环边界多写等号、访问i1打印i和数组长度检查边界条件NullPointerException引用类型数组元素未初始化初始化数组时逐元素赋值或填充数组UnsupportedOperationExceptionArrays.asList后调用add/remove用new ArrayList包裹ConcurrentModificationException遍历时修改List结构用迭代器或收集到新列表再处理NumberFormatException从字符串解析整数时包含空格trim后再parse整型溢出累加和超过Integer范围改用long记录中间结果第5条我特别有感触笔试里很多输入带空格比如1, 2, 3split后每个元素前后可能都有空格直接Integer.parseInt就会抛异常。所以我在所有parse之前都会先trim()这个习惯已经刻进肌肉记忆了。5.2 面试官喜欢追问的5个方向数组题大部分都有明显的“追问链”你给出一个解法后面试官会逐步加条件看你能否举一反三。我总结过一轮高频追问写下来供参考。第一个追问方向是空间复杂度。比如“两数之和”你用了HashMap面试官会问能不能不用额外空间。这时数组有序可以用双指针降到O(1)空间无序则要先排序再双指针时间复杂度变成O(n log n)。第二个追问方向是数组是否有序。很多题默认数组无序一旦加了这个条件解法可能完全不同。例如“两数之和”变得简单“三数之和”可以配合双指针直接去除HashMap。第三个追问方向是有没有负数。“和为K的子数组”如果有负数就不能用滑动窗口面试官会专门选这种边界情况来测试你对算法适用条件的理解。回答“因为负数破坏了滑窗的单调性”比直接写代码更显功力。第四个追问方向是数据规模。数据量在几千时O(n^2)问题不大到了百万级别就必须O(n log n)甚至O(n)。面试官可能拿“最大子数组和”问你数据量大到内存装不下怎么办这就涉及分治和流式处理了。第五个追问方向是变体应用题。把“移动零”改成“把奇数移到前面偶数移到后面”或者把“合并区间”改成“插入一个新区间并合并”这些变体看着新鲜但底层套路一样练熟了基本就是换皮。5.3 我自己的诊断思路定位Bug从哪开始刷数组题遇到Bug时我最不推荐的做法是盯着代码反复读。人眼对熟悉的代码有很强的“脑补”能力越看越觉得自己写的没错。我的经验是先用最小用例跑一遍把每次循环的变量值打印出来跟手算结果对比。比如处理“移动零”时我遇到过一次结果不对的情况就在交换前后打印slow、fast和整个数组立刻发现是慢指针没有在交换后递增。这个错误用肉眼盯着代码其实很容易发现但在高压环境下经常被忽略。打印调试法看似笨其实是定位这类逻辑错误最快的方式。另一个技巧是“增量验证”不要等整道题全写完再跑写到一个关键节点就分步验证一次。比如“合并区间”里先只写排序并打印结果确认排序正确后再写合并逻辑。分段调试虽然多花几分钟但能大幅降低整段代码出错后无处下手的概率。6. 刷完这一轮我总结出的三条学习建议第一一定要按套路分组刷题不要按题号顺序硬刷。我自己用“专题刷题法”建立分类表格后复习效率提升了不止一倍。每道题除了记录解法标签我还额外写了一句“这道题坑在哪”比如“和为K的子数组要初始化prefixCount.put(0,1)”“合并区间注意排序规则”。这样的备注才是属于自己的原创题解比复制粘贴官方题解有价值得多。第二每道题写完代码后试着自己从头讲一遍解题思路。能讲清楚说明真的懂了讲不清楚或者讲到一半卡住说明理解还处在“背模板”阶段。这个办法我一开始也觉得挺麻烦但坚持几周后发现面试时被问到解题原理我的反应速度比之前快了很多。第三代码一定要达到“能跑、能改、能背”三个标准。“能跑”指提交通过“能改”指面对面试官改变条件时能快速调整代码“能背”不是死记硬背而是能不看题解直接从零手写核心片段。Hot 100的数组题刷到这里我最大的体会是算法题的进步不是线性的而是平台期之后突然跳一跳。前面几十道题刷得想吐最后一轮整理笔记时才发现好多题目之间根本就是同一个套路换了个故事背景数组题也是这样摸透了它们后面的链表和矩阵题就会顺很多。