先说我自己的结论连续辅导过几届校招生刷hot100之后我发现数组类题目是整份题单里“投入产出比”最高、但也是最容易被低估的板块。很多人觉得数组题就是遍历循环加几个边界判断结果一上笔试就被“最长连续序列”“合并区间”“接雨水”这类中等题教做人。这篇笔记我不打算做题目搬运而是把hot100里真正属于数组范畴的高频题按底层技法重新归类结合Java语言特性整理成一份能直接拿去复习的方法论包含核心思路、复杂度分析、实现细节和我在面试中被问过的变体。1. 数组题在hot100里的真实地位与学习路径建议先给一份自测清单。hot100虽然不是官方题单但已经是Java后端面试默认的题库事实标准。数一下其中能用“数组技巧”直接或间接解决的题目大概超过40道覆盖面非常大。很多你以为属于“哈希表”“双指针”“滑动窗口”的题本质都是数组操作的延伸。数组三件套题两数之和、三数之和、盛最多水的容器连续子数组题最大子数组和、和为K的子数组、滑动窗口最大值原地处理题移动零、除自身以外数组的乘积、合并区间矩阵走位题螺旋矩阵、旋转图像、搜索二维矩阵二分边界题在排序数组中查找元素的第一个和最后一个位置、搜索旋转排序数组我对不同基础的读者有不同建议。如果你刚开始准备不要按hot100原始编号顺序刷那样会今天哈希明天树脑内上下文一直切来切去。正确做法是按技法分组一组组突破。数组类正好是整套方法论的入门钥匙因为它的数据结构足够简单你能把所有注意力集中在思考“指针怎么移动”“区间怎么维护”上而不是先被树和图的递归吓退。关于“热题100”和“代码随想录”“剑指Offer”之间的关系我的判断是第一轮以hot100为主轴遇到不会的题去代码随想录看对应专题文章剑指Offer可以在面试前一周用来弱项补漏。注意priority是“能解释清楚思路”比“AC过”重要得多这点在面试环节尤为关键我会在第四部分专门讲。补一句个人体会刷数组题最快的成长路径不是看题解而是“先尝试暴力解再对着最优解找差距”。数组题的暴力解往往只需要两层循环逻辑很好想难的是从O(n²)往O(n)跳的那一步而这一步背后的依据永远只有三类哈希换时间、双指针消去一层循环、前缀和把区间查询变成前缀差值。2. 数组题核心技法拆解哈希、双指针、前缀和、滑动窗口数组题看似题型五花八门落到代码层面其实只有几套固定的思维模型。如果你能把这几套模型吃透hot100里的数组题至少能秒掉一半。下面逐个拆。2.1 哈希表辅助怎么把O(n²)暴力“变”成O(n)最典型的就是两数之和。暴力的做法是固定一个i再从i1往后找另一个数复杂度O(n²)。哈希优化的核心逻辑是与其每次都去后面“找”不如用一个HashMap把已经扫过的值存下来这样每个元素只需要问一次“target - 当前值在不在之前的集合里”。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[0]; }这个题要重点理解的不是代码本身而是**“什么时候才应该用哈希表”**。我总结的判据是当题目中的“查找某个元素是否存在”“统计某个值出现的次数”成为了主操作并且每次查找如果都要遍历那就可以用哈希把单次查找从O(n)降为O(1)。hot100里另一个非常值得吃透的哈希数组题是最长连续序列。题目要求找出数字连续的最长序列比如[100, 4, 200, 1, 3, 2]结果是[1,2,3,4]长度4。这个题最容易被误导去排序但排序是O(nlogn)题目明确要求O(n)就得用别的手段。标准解法是先把所有数字放进HashSet然后只对“序列起点”的数向后累加查找。判断“序列起点”的技巧是如果num - 1在集合里说明num不是起点直接跳过只有num - 1不存在时才继续往后数。这一步非常关键保证了每个数最多被访问两次整体复杂度才能控制在O(n)。public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) set.add(num); int longest 0; for (int num : set) { if (!set.contains(num - 1)) { int cur num; int len 1; while (set.contains(cur 1)) { cur; len; } longest Math.max(longest, len); } } return longest; }面试里如果时间紧张这个题可以先讲“每个序列只能从起点开始数”面试官往往就会点头因为他知道你不是背的题解而是真的理解去重和起点的价值。2.2 双指针原地处理的灵魂也是数组题最高频的代码骨架双指针分两种。一种是相向双指针常用于有序数组或者“从两端逼近”的场景代表题是三数之和和盛最多水的容器另一种是同向双指针快慢指针常用于原地去重、移动元素代表题是移动零、删除有序数组中的重复项。先说移动零。这题也许很多人觉得简单但它是考察“是否理解稳定性”和“是否理解原地操作”的经典题。暴力做法是开一个新数组把非零元素按序放好再补零但面试官肯定不满意因为额外空间是O(n)。最优解法用快慢指针做交换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; } } }slow始终指向“下一个非零元素应该放置的位置”fast负责扫描所有元素。每当fast找到一个非零值就跟slow位置交换。这个过程保证了两个性质一是所有非零元素保留了原有相对顺序二是所有0被“挤”到了数组末尾。注意slow只有在交换之后才意味着如果数组开头就是非零值fast和slow会指向同一个位置自己和自己交换性能上没有额外损耗。再说三数之和。这个是hot100数组题里考察频率极高的中等题稍不留神就超时。核心在于先排序然后固定一个数i再用相向双指针在i右侧找两数之和为-nums[i]的组合。虽然排序额外用了O(nlogn)但双指针部分把内部的两层循环压缩成了一层整体是O(n²)比三重循环O(n³)好很多。去重逻辑是这个题最大的坑。我最早写的时候在双指针内部使用了set去重结果虽然AC了但面试被追问“能不能不借助额外空间”才发现标准写法是在每次移动指针时跳过重复值public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); for (int i 0; i nums.length - 2; i) { if (i 0 nums[i] nums[i - 1]) continue; int left i 1, right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return res; }你注意看循环里的末尾两行left; right--;这是在做完一次匹配之后必须更新的否则会陷入死循环。此外当nums[i] 0时可以直接break因为数组已排序后面不可能凑出和为0这个剪枝能省不少时间。2.3 前缀和子数组区间求和的标准答案如果一道题让你求“子数组的某种累加性质”比如和为K的子数组你第一个想到的不应该是双循环而是前缀和数组。定义prefix[i] nums[0] nums[1] ... nums[i - 1]那么子数组nums[j...i]的和就是prefix[i1] - prefix[j]。暴力枚举所有j和i仍然是O(n²)真正的优化点在于把问题变成两个前缀和之间的差值等于K再借助HashMap统计前面出现过的前缀和次数。以和为K的子数组为例标准的O(n)解法如下public int subarraySum(int[] nums, int k) { MapInteger, Integer prefixCount new HashMap(); prefixCount.put(0, 1); int sum 0, ans 0; for (int num : nums) { sum num; ans prefixCount.getOrDefault(sum - k, 0); prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) 1); } return ans; }这里面最容易被忽略的细节是prefixCount.put(0, 1)这一行。它表示“前缀和为0的情况出现过1次”考虑了“子数组从0开始到当前位置”这种场景。如果你漏掉这行当整个前缀和刚好等于K的时候就会少算一次代码直接WA。前缀和的套路还可以延伸到除自身以外数组的乘积。这题要求每个位置的结果是“除自己外所有元素的乘积”并且不能用除法。思路是构造左右两个累积数组left[i]表示i左边所有数的乘积right[i]表示右边所有数的乘积最终答案就是left[i] * right[i]。这题我在面试里见过不少变体比如要求空间O(1)从常数种状态降为只用累乘变量建议你把两种写法都练一遍。2.4 滑动窗口连续区间的“可持续维护”滑动窗口本质上是一种特殊的双指针只不过两个指针只朝同一方向移动且中间维护的“窗口”可以看作一种可变长度的连续区间。hot100里最典型的数组滑动窗口题是无重复字符的最长子串这题虽然是字符串技巧同数组以及滑动窗口最大值。后者是个中等偏上的题Naive的O(nk)解法是每步扫描窗口内最大值但optimal方案涉及Deque双端队列维护窗口内“可能成为最大值的元素下标”。public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length 0) return new int[0]; int[] ans new int[nums.length - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i nums.length; i) { if (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); if (i k - 1) { ans[i - k 1] nums[deque.peekFirst()]; } } return ans; }这里也是Java细节多的地方Deque接口的peekFirst/pollFirst/offerLast分别对应栈和队列操作如果用错了方法边界判断就会出错。为什么用下标而不是值因为需要判断窗口是否过期只用值无法判断。3. Java实现数组题最容易踩的坑排序、拷贝、集合转换标题里既然带了“JAVA”三个字那就必须聊聊Java语言本身在解数组题时那些防不胜防的实现细节。这些坑我敢说九成新手都踩过有部分老手如果没刷过几遍也未必能立刻反应过来。3.1 排序的三种写法和一个隐藏的性能陷阱数组排序写法有三类// 写法1基本类型数组升序 Arrays.sort(nums); // 写法2封装类型数组可以传Comparator实现降序 Integer[] boxed Arrays.stream(nums).boxed().toArray(Integer[]::new); Arrays.sort(boxed, (a, b) - b - a); // 写法3二维数组按某个维度排序合并区间题必用 Arrays.sort(intervals, (a, b) - a[0] - b[0]);排序这里最大的坑在于Java对int[]采用的是双轴快排Dual-Pivot Quicksort对对象数组采用的是TimSort归并排序的优化版两者时间复杂度在最好、最坏情况下的表现不同。对于基本类型数组双轴快排的时间复杂度平均O(nlogn)、最坏O(n²)但实际工程优化到位一般不会触发最坏情况对象数组的TimSort无论何种输入都能保证O(nlogn)。刷题时几乎不用刻意关心这一点但面试官如果追问“为什么Java的Arrays.sort对不同类型有不同策略”你要能答出“基本类型需要稳定性不高、快排原地排序省空间对象类型要求稳定排序归并变体更合适”。另一个实际问题是很多人在Arrays.sort里写(a, b) - b - a如果两个数相差很大比如b Integer.MAX_VALUE, a -1会溢出变成负数导致排序结果错误。正确写法是Integer.compare(b, a)。3.2 数组的初始化、拷贝和“扩容”操作数组定长是Java新手最不舒服的点。我们解数组题时经常需要动态往数组里加元素比如螺旋矩阵的结果集长度未知。这时候有两个选择一是用ArrayList收集最后转数组二是先开一个大数组再Arrays.copyOf截断。这两个方案没有绝对优劣我按场景给建议结果集长度不确定优先ListInteger收集结果集长度可以推算比如螺旋矩阵的m*n直接预先分配固定数组避免装箱开销需要合并两个数组时用System.arraycopy或Arrays.copyOf后者是前者的封装语义更清晰int[] arr new int[]{1, 2, 3}; int[] expanded Arrays.copyOf(arr, arr.length 1); expanded[arr.length] 4;如果你在做笔试且内存限制较紧尽量少用Integer和ListInteger的自动装箱改用Listint[]存区间或坐标能省不少内存。3.3 数组转成List和List转数组的“正确姿势”这是个小知识点但面试手撕代码时极常出错。数组转List时如果你写Arrays.asList(arr)先想想arr是不是Integer[]而不是int[]。Arrays.asList接收的是泛型可变参数int[]会被当作一个整体元素而不是展开成多个元素返回的List里只有一个元素——这会让你在“求最大值所在下标”这类题里哭出来。正确处理方式Integer[] arr new Integer[]{1, 2, 3}; ListInteger list Arrays.asList(arr); // 如果是基本类型int[]需要先boxed ListInteger list2 Arrays.stream(intArr).boxed().collect(Collectors.toList());反向转换也不难// ListInteger - int[] int[] arr list.stream().mapToInt(Integer::intValue).toArray();注意Arrays.asList返回的List是不可变长度视图调用add会抛UnsupportedOperationException。如果你后续要往集合里加元素必须在自己创建的ArrayList里初始化。4. 高频数组题逐题拆解从暴力到最优的完整思考链路理论讲再多不如以身试法。这一节我挑几道hot100里代表性强的数组题把“从暴力到最优”的完整思考过程呈现出来。每道题我都会标注面试官可能的追问点。4.1 除自身以外数组的乘积空间复杂度是怎么一步步降下来的题目要求计算出answer[i] 除nums[i]外所有元素的乘积不允许用除法。这题有意思的地方在于思维链条非常长特别适合面试官用来层层逼问。阶段一暴力想法对于每个i都遍历一遍所有元素求积再除以nums[i]。但题目不允许除法而且时间复杂度O(n²)肯定不是好答案。阶段二左右前缀积定义left[i]为i左侧所有元素的乘积right[i]为右侧所有元素的乘积。answer[i] left[i] * right[i]。这个方案O(n)时间O(n)空间。public int[] productExceptSelf(int[] nums) { int n nums.length; int[] left new int[n]; int[] right new int[n]; left[0] 1; for (int i 1; i n; i) { left[i] left[i - 1] * nums[i - 1]; } right[n - 1] 1; for (int i n - 2; i 0; i--) { right[i] right[i 1] * nums[i 1]; } int[] ans new int[n]; for (int i 0; i n; i) { ans[i] left[i] * right[i]; } return ans; }阶段三O(1)额外空间题目进阶要求“常数空间”。进一步观察可以发现先用ans数组保存左累积结果然后从右向左遍历时用一个变量rightProduct不断累乘右侧元素直接原地更新ans[i]。public int[] productExceptSelf(int[] nums) { int n nums.length; int[] ans new int[n]; ans[0] 1; for (int i 1; i n; i) { ans[i] ans[i - 1] * nums[i - 1]; } int rightProduct 1; for (int i n - 1; i 0; i--) { ans[i] * rightProduct; rightProduct * nums[i]; } return ans; }这里面的关键点在于理解遍历方向右边前缀积的累乘是从数组尾部开始的因为“右边的乘积”对越靠右的元素来说越少。我当时第一次写反了方向结果从右往左算的时候把nums[0]也乘进去了debug好久才意识到。4.2 合并区间排序维度与边界条件的实证分析合并区间这题考察的是“是否有清晰的数据结构组织区间”以及“是否会处理相邻区间的四种关系”。个人感觉这题比多数hard题更能筛选候选人因为它在15分钟内基本能止步于“会写双循环”和“真正理解排序后合并”这两个档次。public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] merged new ArrayList(); for (int[] interval : intervals) { if (merged.isEmpty() || merged.get(merged.size() - 1)[1] interval[0]) { merged.add(interval); } else { merged.get(merged.size() - 1)[1] Math.max(merged.get(merged.size() - 1)[1], interval[1]); } } return merged.toArray(new int[merged.size()][]); }我列的四种关系是完全包含、重叠部分、端点相接比如[1,2]和[2,3]题目里通常算可合并、完全不相交。排序后只需要处理后继区间与前驱是否有交集处理逻辑从四分类简化成二分支这就是排序带来的收益。面试官常追问的一个变体是“如果区间没有排序怎么处理”答案只能是先排序复杂度O(nlogn)。如果数据规模不大也可以考虑基于map的扫描线但实际工程里排序永远是最稳的。4.3 螺旋矩阵与旋转图像模拟类数组题的通用方法论矩阵类题目在hot100里的占比不低看起来是二维数组的遍历其实考的是“方向感”和“边界维护”。螺旋矩阵的思路可以抽象为维护四个方向的边界top, bottom, left, right按右下左上的顺序一圈一圈向内收缩。public ListInteger spiralOrder(int[][] matrix) { ListInteger res new ArrayList(); int top 0, bottom matrix.length - 1; int left 0, right matrix[0].length - 1; while (top bottom left right) { for (int j left; j right; j) res.add(matrix[top][j]); top; for (int i top; i bottom; i) res.add(matrix[i][right]); right--; if (top bottom) { for (int j right; j left; j--) res.add(matrix[bottom][j]); bottom--; } if (left right) { for (int i bottom; i top; i--) res.add(matrix[i][left]); left; } } return res; }注意到两行if (top bottom)和if (left right)这是防止最后一圈只剩一行或一列时重复遍历。丢掉任何一个if在非方阵的情况下就会下标越界。考这道题时面试官就是想看你能不能考虑这些不对称情况。旋转图像其实可以当成一种“位置映射题”。把矩阵顺时针旋转90度最优雅的做法是“先按主对角线翻转再按垂直中轴翻转”。public void rotate(int[][] matrix) { int n matrix.length; for (int i 0; i n; i) { for (int j i 1; j n; j) { int tmp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] tmp; } } for (int i 0; i n; i) { for (int j 0; j n / 2; j) { int tmp matrix[i][j]; matrix[i][j] matrix[i][n - 1 - j]; matrix[i][n - 1 - j] tmp; } } }初学的时候我不理解为什么要分两步后来意识到对角线翻转把“行”映射成“列”垂直翻转再完成水平方向的倒序两步矩阵变换的复合就是旋转90度。如果你忘了这个组合傻乎乎地在原数组上直接交换四个位置坐标非常容易搞混。背下“二段翻转法”比背四个点的轮换公式要安全得多。5. 面试实战向怎么讲数组题才能让面试官点头刷题和面试是两回事。代码能跑通只是最低标准面试官更在意你能不能把思路讲清楚遇到边界条件能不能快速反应。这里分享一些我在面试别人和被别人面之后总结的表达框架。5.1 先说暴力再聊优化用“复杂度阻力”驱动思路推进很多人一上来就讲最优解反而会让面试官怀疑你是不是背的。正确的打开方式是先给一个最直观的暴力枚举思路用一句话说清楚时空复杂度指出复杂度的瓶颈在哪最常见的是“每次查找都要遍历整个数组”“每轮都重复计算区间和”针对瓶颈选择对应的优化手段哈希、双指针、前缀和、滑动窗口描述优化后复杂度并和暴力方案对比比如两数之和“暴力是固定i然后遍历i后面的所有数O(n²)。因为每次找值都是在遍历我想用一个哈希表把遍历过的值存起来这样每次查找变成O(1)整体降到O(n)。”这个表达比直接背出HashMap解法更有说服力因为面试官看到的是一套思考模式而不是记忆片段。5.2 边界条件要在讲完思路后主动补充数组题的边界条件就是那几个空数组、长度为1、全部相同元素、已经有序、数值溢出、矩阵只有一行或一列。你不一定每一个都要写上代码但至少要能在口头上说“这里我要注意空数组会越界”“移动零要注意非零元素在开头时光标重合的情况”“乘积累计需要防止int溢出必要时用long”。我自己在面试中吃过亏的是“在排序数组中查找元素的第一个和最后一个位置”这道题一上来就写二分结果忽略了nums长度为0的情况当场翻车。从那以后我养成了个坏习惯——写任何数组题之前把空数组的三行防御先写上if (nums null || nums.length 0) { return -1; // 或者new int[]{-1, -1}视题目要求而定 }这个习惯笔试里能救回不少分。5.3 我的刷题节奏和笔记方法最后聊聊怎么安排时间。如果你离面试还有三个月我建议前两周只刷数组题按这篇笔记里的四类技法对hot100中的数组题做分组练习每天3到5道。刷的时候不要只追求AC每道题在提交通过之后立刻在题解区找一篇评论数最高的题解对比自己的代码把“为什么别人的能少一个变量”“为什么别人的代码能少一个分类讨论”写进笔记。我不推荐用编辑器里带debug反复试错而是推荐用纸笔先模拟一遍流程比如三数之和的双指针是怎么从两端逼近的在纸上画一个有序数组手动走一遍指针移动比任何调试都更有效果。数组题的抽象程度相对较低用纸笔画图正好能把这层抽象直观化这也会让你面试讲思路时不至于卡壳。面试前一周把这些题的二刷清单再过一遍重点看自己笔记里标红的地方比如HashMap初始容量的选择HashMap(n)避免扩容、双指针的while条件里要不要加等号这通常决定了区间端点是否闭合等等。这些细节就是筛掉一大批人的地方。写在最后的小建议数组是真功夫这类题的解法套路一共就那几板斧但你能不能在面试高压下判断出“该用哪一板斧”才是分水岭。把hot100里数组类题目吃透不只是为了应付那些数组题本身更是因为后续的哈希、双指针、滑动窗口专题全都要建立在这套基本功之上。磨刀不误砍柴工这个板块值得你多花一点时间也值得你在简历上自信地写上“熟悉常用数据结构与算法”。 LeetCode Hot100数组题刷题方法论：哈希、双指针、前缀和与滑动窗口
先说我自己的结论连续辅导过几届校招生刷hot100之后我发现数组类题目是整份题单里“投入产出比”最高、但也是最容易被低估的板块。很多人觉得数组题就是遍历循环加几个边界判断结果一上笔试就被“最长连续序列”“合并区间”“接雨水”这类中等题教做人。这篇笔记我不打算做题目搬运而是把hot100里真正属于数组范畴的高频题按底层技法重新归类结合Java语言特性整理成一份能直接拿去复习的方法论包含核心思路、复杂度分析、实现细节和我在面试中被问过的变体。1. 数组题在hot100里的真实地位与学习路径建议先给一份自测清单。hot100虽然不是官方题单但已经是Java后端面试默认的题库事实标准。数一下其中能用“数组技巧”直接或间接解决的题目大概超过40道覆盖面非常大。很多你以为属于“哈希表”“双指针”“滑动窗口”的题本质都是数组操作的延伸。数组三件套题两数之和、三数之和、盛最多水的容器连续子数组题最大子数组和、和为K的子数组、滑动窗口最大值原地处理题移动零、除自身以外数组的乘积、合并区间矩阵走位题螺旋矩阵、旋转图像、搜索二维矩阵二分边界题在排序数组中查找元素的第一个和最后一个位置、搜索旋转排序数组我对不同基础的读者有不同建议。如果你刚开始准备不要按hot100原始编号顺序刷那样会今天哈希明天树脑内上下文一直切来切去。正确做法是按技法分组一组组突破。数组类正好是整套方法论的入门钥匙因为它的数据结构足够简单你能把所有注意力集中在思考“指针怎么移动”“区间怎么维护”上而不是先被树和图的递归吓退。关于“热题100”和“代码随想录”“剑指Offer”之间的关系我的判断是第一轮以hot100为主轴遇到不会的题去代码随想录看对应专题文章剑指Offer可以在面试前一周用来弱项补漏。注意priority是“能解释清楚思路”比“AC过”重要得多这点在面试环节尤为关键我会在第四部分专门讲。补一句个人体会刷数组题最快的成长路径不是看题解而是“先尝试暴力解再对着最优解找差距”。数组题的暴力解往往只需要两层循环逻辑很好想难的是从O(n²)往O(n)跳的那一步而这一步背后的依据永远只有三类哈希换时间、双指针消去一层循环、前缀和把区间查询变成前缀差值。2. 数组题核心技法拆解哈希、双指针、前缀和、滑动窗口数组题看似题型五花八门落到代码层面其实只有几套固定的思维模型。如果你能把这几套模型吃透hot100里的数组题至少能秒掉一半。下面逐个拆。2.1 哈希表辅助怎么把O(n²)暴力“变”成O(n)最典型的就是两数之和。暴力的做法是固定一个i再从i1往后找另一个数复杂度O(n²)。哈希优化的核心逻辑是与其每次都去后面“找”不如用一个HashMap把已经扫过的值存下来这样每个元素只需要问一次“target - 当前值在不在之前的集合里”。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[0]; }这个题要重点理解的不是代码本身而是**“什么时候才应该用哈希表”**。我总结的判据是当题目中的“查找某个元素是否存在”“统计某个值出现的次数”成为了主操作并且每次查找如果都要遍历那就可以用哈希把单次查找从O(n)降为O(1)。hot100里另一个非常值得吃透的哈希数组题是最长连续序列。题目要求找出数字连续的最长序列比如[100, 4, 200, 1, 3, 2]结果是[1,2,3,4]长度4。这个题最容易被误导去排序但排序是O(nlogn)题目明确要求O(n)就得用别的手段。标准解法是先把所有数字放进HashSet然后只对“序列起点”的数向后累加查找。判断“序列起点”的技巧是如果num - 1在集合里说明num不是起点直接跳过只有num - 1不存在时才继续往后数。这一步非常关键保证了每个数最多被访问两次整体复杂度才能控制在O(n)。public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) set.add(num); int longest 0; for (int num : set) { if (!set.contains(num - 1)) { int cur num; int len 1; while (set.contains(cur 1)) { cur; len; } longest Math.max(longest, len); } } return longest; }面试里如果时间紧张这个题可以先讲“每个序列只能从起点开始数”面试官往往就会点头因为他知道你不是背的题解而是真的理解去重和起点的价值。2.2 双指针原地处理的灵魂也是数组题最高频的代码骨架双指针分两种。一种是相向双指针常用于有序数组或者“从两端逼近”的场景代表题是三数之和和盛最多水的容器另一种是同向双指针快慢指针常用于原地去重、移动元素代表题是移动零、删除有序数组中的重复项。先说移动零。这题也许很多人觉得简单但它是考察“是否理解稳定性”和“是否理解原地操作”的经典题。暴力做法是开一个新数组把非零元素按序放好再补零但面试官肯定不满意因为额外空间是O(n)。最优解法用快慢指针做交换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; } } }slow始终指向“下一个非零元素应该放置的位置”fast负责扫描所有元素。每当fast找到一个非零值就跟slow位置交换。这个过程保证了两个性质一是所有非零元素保留了原有相对顺序二是所有0被“挤”到了数组末尾。注意slow只有在交换之后才意味着如果数组开头就是非零值fast和slow会指向同一个位置自己和自己交换性能上没有额外损耗。再说三数之和。这个是hot100数组题里考察频率极高的中等题稍不留神就超时。核心在于先排序然后固定一个数i再用相向双指针在i右侧找两数之和为-nums[i]的组合。虽然排序额外用了O(nlogn)但双指针部分把内部的两层循环压缩成了一层整体是O(n²)比三重循环O(n³)好很多。去重逻辑是这个题最大的坑。我最早写的时候在双指针内部使用了set去重结果虽然AC了但面试被追问“能不能不借助额外空间”才发现标准写法是在每次移动指针时跳过重复值public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); for (int i 0; i nums.length - 2; i) { if (i 0 nums[i] nums[i - 1]) continue; int left i 1, right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return res; }你注意看循环里的末尾两行left; right--;这是在做完一次匹配之后必须更新的否则会陷入死循环。此外当nums[i] 0时可以直接break因为数组已排序后面不可能凑出和为0这个剪枝能省不少时间。2.3 前缀和子数组区间求和的标准答案如果一道题让你求“子数组的某种累加性质”比如和为K的子数组你第一个想到的不应该是双循环而是前缀和数组。定义prefix[i] nums[0] nums[1] ... nums[i - 1]那么子数组nums[j...i]的和就是prefix[i1] - prefix[j]。暴力枚举所有j和i仍然是O(n²)真正的优化点在于把问题变成两个前缀和之间的差值等于K再借助HashMap统计前面出现过的前缀和次数。以和为K的子数组为例标准的O(n)解法如下public int subarraySum(int[] nums, int k) { MapInteger, Integer prefixCount new HashMap(); prefixCount.put(0, 1); int sum 0, ans 0; for (int num : nums) { sum num; ans prefixCount.getOrDefault(sum - k, 0); prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) 1); } return ans; }这里面最容易被忽略的细节是prefixCount.put(0, 1)这一行。它表示“前缀和为0的情况出现过1次”考虑了“子数组从0开始到当前位置”这种场景。如果你漏掉这行当整个前缀和刚好等于K的时候就会少算一次代码直接WA。前缀和的套路还可以延伸到除自身以外数组的乘积。这题要求每个位置的结果是“除自己外所有元素的乘积”并且不能用除法。思路是构造左右两个累积数组left[i]表示i左边所有数的乘积right[i]表示右边所有数的乘积最终答案就是left[i] * right[i]。这题我在面试里见过不少变体比如要求空间O(1)从常数种状态降为只用累乘变量建议你把两种写法都练一遍。2.4 滑动窗口连续区间的“可持续维护”滑动窗口本质上是一种特殊的双指针只不过两个指针只朝同一方向移动且中间维护的“窗口”可以看作一种可变长度的连续区间。hot100里最典型的数组滑动窗口题是无重复字符的最长子串这题虽然是字符串技巧同数组以及滑动窗口最大值。后者是个中等偏上的题Naive的O(nk)解法是每步扫描窗口内最大值但optimal方案涉及Deque双端队列维护窗口内“可能成为最大值的元素下标”。public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length 0) return new int[0]; int[] ans new int[nums.length - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i nums.length; i) { if (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); if (i k - 1) { ans[i - k 1] nums[deque.peekFirst()]; } } return ans; }这里也是Java细节多的地方Deque接口的peekFirst/pollFirst/offerLast分别对应栈和队列操作如果用错了方法边界判断就会出错。为什么用下标而不是值因为需要判断窗口是否过期只用值无法判断。3. Java实现数组题最容易踩的坑排序、拷贝、集合转换标题里既然带了“JAVA”三个字那就必须聊聊Java语言本身在解数组题时那些防不胜防的实现细节。这些坑我敢说九成新手都踩过有部分老手如果没刷过几遍也未必能立刻反应过来。3.1 排序的三种写法和一个隐藏的性能陷阱数组排序写法有三类// 写法1基本类型数组升序 Arrays.sort(nums); // 写法2封装类型数组可以传Comparator实现降序 Integer[] boxed Arrays.stream(nums).boxed().toArray(Integer[]::new); Arrays.sort(boxed, (a, b) - b - a); // 写法3二维数组按某个维度排序合并区间题必用 Arrays.sort(intervals, (a, b) - a[0] - b[0]);排序这里最大的坑在于Java对int[]采用的是双轴快排Dual-Pivot Quicksort对对象数组采用的是TimSort归并排序的优化版两者时间复杂度在最好、最坏情况下的表现不同。对于基本类型数组双轴快排的时间复杂度平均O(nlogn)、最坏O(n²)但实际工程优化到位一般不会触发最坏情况对象数组的TimSort无论何种输入都能保证O(nlogn)。刷题时几乎不用刻意关心这一点但面试官如果追问“为什么Java的Arrays.sort对不同类型有不同策略”你要能答出“基本类型需要稳定性不高、快排原地排序省空间对象类型要求稳定排序归并变体更合适”。另一个实际问题是很多人在Arrays.sort里写(a, b) - b - a如果两个数相差很大比如b Integer.MAX_VALUE, a -1会溢出变成负数导致排序结果错误。正确写法是Integer.compare(b, a)。3.2 数组的初始化、拷贝和“扩容”操作数组定长是Java新手最不舒服的点。我们解数组题时经常需要动态往数组里加元素比如螺旋矩阵的结果集长度未知。这时候有两个选择一是用ArrayList收集最后转数组二是先开一个大数组再Arrays.copyOf截断。这两个方案没有绝对优劣我按场景给建议结果集长度不确定优先ListInteger收集结果集长度可以推算比如螺旋矩阵的m*n直接预先分配固定数组避免装箱开销需要合并两个数组时用System.arraycopy或Arrays.copyOf后者是前者的封装语义更清晰int[] arr new int[]{1, 2, 3}; int[] expanded Arrays.copyOf(arr, arr.length 1); expanded[arr.length] 4;如果你在做笔试且内存限制较紧尽量少用Integer和ListInteger的自动装箱改用Listint[]存区间或坐标能省不少内存。3.3 数组转成List和List转数组的“正确姿势”这是个小知识点但面试手撕代码时极常出错。数组转List时如果你写Arrays.asList(arr)先想想arr是不是Integer[]而不是int[]。Arrays.asList接收的是泛型可变参数int[]会被当作一个整体元素而不是展开成多个元素返回的List里只有一个元素——这会让你在“求最大值所在下标”这类题里哭出来。正确处理方式Integer[] arr new Integer[]{1, 2, 3}; ListInteger list Arrays.asList(arr); // 如果是基本类型int[]需要先boxed ListInteger list2 Arrays.stream(intArr).boxed().collect(Collectors.toList());反向转换也不难// ListInteger - int[] int[] arr list.stream().mapToInt(Integer::intValue).toArray();注意Arrays.asList返回的List是不可变长度视图调用add会抛UnsupportedOperationException。如果你后续要往集合里加元素必须在自己创建的ArrayList里初始化。4. 高频数组题逐题拆解从暴力到最优的完整思考链路理论讲再多不如以身试法。这一节我挑几道hot100里代表性强的数组题把“从暴力到最优”的完整思考过程呈现出来。每道题我都会标注面试官可能的追问点。4.1 除自身以外数组的乘积空间复杂度是怎么一步步降下来的题目要求计算出answer[i] 除nums[i]外所有元素的乘积不允许用除法。这题有意思的地方在于思维链条非常长特别适合面试官用来层层逼问。阶段一暴力想法对于每个i都遍历一遍所有元素求积再除以nums[i]。但题目不允许除法而且时间复杂度O(n²)肯定不是好答案。阶段二左右前缀积定义left[i]为i左侧所有元素的乘积right[i]为右侧所有元素的乘积。answer[i] left[i] * right[i]。这个方案O(n)时间O(n)空间。public int[] productExceptSelf(int[] nums) { int n nums.length; int[] left new int[n]; int[] right new int[n]; left[0] 1; for (int i 1; i n; i) { left[i] left[i - 1] * nums[i - 1]; } right[n - 1] 1; for (int i n - 2; i 0; i--) { right[i] right[i 1] * nums[i 1]; } int[] ans new int[n]; for (int i 0; i n; i) { ans[i] left[i] * right[i]; } return ans; }阶段三O(1)额外空间题目进阶要求“常数空间”。进一步观察可以发现先用ans数组保存左累积结果然后从右向左遍历时用一个变量rightProduct不断累乘右侧元素直接原地更新ans[i]。public int[] productExceptSelf(int[] nums) { int n nums.length; int[] ans new int[n]; ans[0] 1; for (int i 1; i n; i) { ans[i] ans[i - 1] * nums[i - 1]; } int rightProduct 1; for (int i n - 1; i 0; i--) { ans[i] * rightProduct; rightProduct * nums[i]; } return ans; }这里面的关键点在于理解遍历方向右边前缀积的累乘是从数组尾部开始的因为“右边的乘积”对越靠右的元素来说越少。我当时第一次写反了方向结果从右往左算的时候把nums[0]也乘进去了debug好久才意识到。4.2 合并区间排序维度与边界条件的实证分析合并区间这题考察的是“是否有清晰的数据结构组织区间”以及“是否会处理相邻区间的四种关系”。个人感觉这题比多数hard题更能筛选候选人因为它在15分钟内基本能止步于“会写双循环”和“真正理解排序后合并”这两个档次。public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] merged new ArrayList(); for (int[] interval : intervals) { if (merged.isEmpty() || merged.get(merged.size() - 1)[1] interval[0]) { merged.add(interval); } else { merged.get(merged.size() - 1)[1] Math.max(merged.get(merged.size() - 1)[1], interval[1]); } } return merged.toArray(new int[merged.size()][]); }我列的四种关系是完全包含、重叠部分、端点相接比如[1,2]和[2,3]题目里通常算可合并、完全不相交。排序后只需要处理后继区间与前驱是否有交集处理逻辑从四分类简化成二分支这就是排序带来的收益。面试官常追问的一个变体是“如果区间没有排序怎么处理”答案只能是先排序复杂度O(nlogn)。如果数据规模不大也可以考虑基于map的扫描线但实际工程里排序永远是最稳的。4.3 螺旋矩阵与旋转图像模拟类数组题的通用方法论矩阵类题目在hot100里的占比不低看起来是二维数组的遍历其实考的是“方向感”和“边界维护”。螺旋矩阵的思路可以抽象为维护四个方向的边界top, bottom, left, right按右下左上的顺序一圈一圈向内收缩。public ListInteger spiralOrder(int[][] matrix) { ListInteger res new ArrayList(); int top 0, bottom matrix.length - 1; int left 0, right matrix[0].length - 1; while (top bottom left right) { for (int j left; j right; j) res.add(matrix[top][j]); top; for (int i top; i bottom; i) res.add(matrix[i][right]); right--; if (top bottom) { for (int j right; j left; j--) res.add(matrix[bottom][j]); bottom--; } if (left right) { for (int i bottom; i top; i--) res.add(matrix[i][left]); left; } } return res; }注意到两行if (top bottom)和if (left right)这是防止最后一圈只剩一行或一列时重复遍历。丢掉任何一个if在非方阵的情况下就会下标越界。考这道题时面试官就是想看你能不能考虑这些不对称情况。旋转图像其实可以当成一种“位置映射题”。把矩阵顺时针旋转90度最优雅的做法是“先按主对角线翻转再按垂直中轴翻转”。public void rotate(int[][] matrix) { int n matrix.length; for (int i 0; i n; i) { for (int j i 1; j n; j) { int tmp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] tmp; } } for (int i 0; i n; i) { for (int j 0; j n / 2; j) { int tmp matrix[i][j]; matrix[i][j] matrix[i][n - 1 - j]; matrix[i][n - 1 - j] tmp; } } }初学的时候我不理解为什么要分两步后来意识到对角线翻转把“行”映射成“列”垂直翻转再完成水平方向的倒序两步矩阵变换的复合就是旋转90度。如果你忘了这个组合傻乎乎地在原数组上直接交换四个位置坐标非常容易搞混。背下“二段翻转法”比背四个点的轮换公式要安全得多。5. 面试实战向怎么讲数组题才能让面试官点头刷题和面试是两回事。代码能跑通只是最低标准面试官更在意你能不能把思路讲清楚遇到边界条件能不能快速反应。这里分享一些我在面试别人和被别人面之后总结的表达框架。5.1 先说暴力再聊优化用“复杂度阻力”驱动思路推进很多人一上来就讲最优解反而会让面试官怀疑你是不是背的。正确的打开方式是先给一个最直观的暴力枚举思路用一句话说清楚时空复杂度指出复杂度的瓶颈在哪最常见的是“每次查找都要遍历整个数组”“每轮都重复计算区间和”针对瓶颈选择对应的优化手段哈希、双指针、前缀和、滑动窗口描述优化后复杂度并和暴力方案对比比如两数之和“暴力是固定i然后遍历i后面的所有数O(n²)。因为每次找值都是在遍历我想用一个哈希表把遍历过的值存起来这样每次查找变成O(1)整体降到O(n)。”这个表达比直接背出HashMap解法更有说服力因为面试官看到的是一套思考模式而不是记忆片段。5.2 边界条件要在讲完思路后主动补充数组题的边界条件就是那几个空数组、长度为1、全部相同元素、已经有序、数值溢出、矩阵只有一行或一列。你不一定每一个都要写上代码但至少要能在口头上说“这里我要注意空数组会越界”“移动零要注意非零元素在开头时光标重合的情况”“乘积累计需要防止int溢出必要时用long”。我自己在面试中吃过亏的是“在排序数组中查找元素的第一个和最后一个位置”这道题一上来就写二分结果忽略了nums长度为0的情况当场翻车。从那以后我养成了个坏习惯——写任何数组题之前把空数组的三行防御先写上if (nums null || nums.length 0) { return -1; // 或者new int[]{-1, -1}视题目要求而定 }这个习惯笔试里能救回不少分。5.3 我的刷题节奏和笔记方法最后聊聊怎么安排时间。如果你离面试还有三个月我建议前两周只刷数组题按这篇笔记里的四类技法对hot100中的数组题做分组练习每天3到5道。刷的时候不要只追求AC每道题在提交通过之后立刻在题解区找一篇评论数最高的题解对比自己的代码把“为什么别人的能少一个变量”“为什么别人的代码能少一个分类讨论”写进笔记。我不推荐用编辑器里带debug反复试错而是推荐用纸笔先模拟一遍流程比如三数之和的双指针是怎么从两端逼近的在纸上画一个有序数组手动走一遍指针移动比任何调试都更有效果。数组题的抽象程度相对较低用纸笔画图正好能把这层抽象直观化这也会让你面试讲思路时不至于卡壳。面试前一周把这些题的二刷清单再过一遍重点看自己笔记里标红的地方比如HashMap初始容量的选择HashMap(n)避免扩容、双指针的while条件里要不要加等号这通常决定了区间端点是否闭合等等。这些细节就是筛掉一大批人的地方。写在最后的小建议数组是真功夫这类题的解法套路一共就那几板斧但你能不能在面试高压下判断出“该用哪一板斧”才是分水岭。把hot100里数组类题目吃透不只是为了应付那些数组题本身更是因为后续的哈希、双指针、滑动窗口专题全都要建立在这套基本功之上。磨刀不误砍柴工这个板块值得你多花一点时间也值得你在简历上自信地写上“熟悉常用数据结构与算法”。