总览本篇包含4道Hot100数组经典题238.除自身以外数组的乘积、189.轮转数组、56.合并区间、53.最大子数组和。数组题型高频技巧前缀/后缀乘积、原地反转、排序贪心、动态规划Kadane算法。238. 除了自身以外数组的乘积思路题目限制不能使用除法核心思路构造前缀数组LL[i] i位置左侧所有元素乘积构造后缀数组RR[i] i位置右侧所有元素乘积answer[i] L[i] * R[i]进阶优化可以不额外开辟L、R数组直接复用输出数组实现O(1)额外空间。classSolution{publicint[]productExceptSelf(int[]nums){intlengthnums.length;// L[i]nums[i]左边所有元素乘积int[]Lnewint[length];// R[i]nums[i]右边所有元素乘积int[]Rnewint[length];int[]answernewint[length];// 最左侧元素左边没有数字初始化为1L[0]1;for(inti1;ilength;i){L[i]nums[i-1]*L[i-1];}// 最右侧元素右边没有数字初始化为1R[length-1]1;for(intilength-2;i0;i--){R[i]nums[i1]*R[i1];}// 当前位置结果 左侧乘积 * 右侧乘积for(inti0;ilength;i){answer[i]L[i]*R[i];}returnanswer;}}复杂度时间复杂度O(n)三次遍历数组空间复杂度O(n)进阶版可压缩至O(1)不计输出数组189. 轮转数组思路题意数组向右轮转k次。注意坑k可能大于数组长度有效轮转次数k k % n。提供两种思路辅助数组法直观简单你截图中的写法原地三次反转法进阶O(1)空间面试优先掌握方法1辅助数组classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;int[]newArrnewint[n];// 取模避免k超过数组长度造成越界kk%n;for(inti0;in;i){// i位置元素轮转后新下标(i k) % nnewArr[(ik)%n]nums[i];}// 将新数组覆盖原数组System.arraycopy(newArr,0,nums,0,n);}}方法2原地反转推荐进阶要求原理整体反转整个数组反转前k个元素反转后面n-k个元素classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;k%n;reverse(nums,0,n-1);// 整体反转reverse(nums,0,k-1);// 反转前k位reverse(nums,k,n-1);// 反转剩余部分}// 反转数组 [start, end] 区间privatevoidreverse(int[]nums,intstart,intend){while(startend){inttempnums[start];nums[start]nums[end];nums[end]temp;start;end--;}}}复杂度辅助数组时间O(n)空间O(n)原地反转时间O(n)空间O(1)56. 合并区间思路贪心算法标准题先按照区间左边界升序排序保证我们从左往右遍历只需要和上一个区间比较使用List保存结果遍历区间当前区间和结果最后一个区间重叠/相接合并更新右边界不重叠直接加入结果集合importjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;classSolution{publicint[][]merge(int[][]intervals){// 第一步按照区间左边界升序排序Arrays.sort(intervals,(a,b)-a[0]-b[0]);Listint[]resnewArrayList();// 先放入第一个区间作为基准res.add(intervals[0]);for(inti1;iintervals.length;i){// 获取结果集合最后一个区间int[]lastres.get(res.size()-1);// 当前遍历区间int[]curintervals[i];if(last[1]cur[0]){// 区间重叠合并更新右边界为两者最大值last[1]Math.max(last[1],cur[1]);}else{// 不重叠直接新增区间res.add(cur);}}// List转为二维数组返回returnres.toArray(newint[res.size()][]);}}复杂度时间复杂度O(n log n)主要开销是排序遍历O(n)空间复杂度O(log n)排序栈开销结果数组不计额外空间53. 最大子数组和Kadane 动态规划思路经典动态规划又叫Kadane算法定义pre以当前下标结尾的最大连续子数组和pre max(nums[i], pre nums[i])含义要么把当前数字接入前面的子数组要么抛弃前面以当前数字作为新子数组起点不断更新全局最大值max。classSolution{publicintmaxSubArray(int[]nums){intpre0;// 初始最大值设为第一个元素兼容全负数数组intmaxnums[0];for(inti0;inums.length;i){intxnums[i];// 选择接上前面子数组 或者 单独以当前元素开头preMath.max(x,prex);// 更新全局最大和maxMath.max(pre,max);}returnmax;}}复杂度时间复杂度O(n)单次遍历空间复杂度O(1)仅使用常数变量题型总结前缀后缀乘积238遇到不能除法、需要排除自身的乘积问题优先前后缀数组思路可尝试空间压缩。数组轮转189面试优先掌握三次反转原地算法辅助数组只能作为基础解法。区间合并56贪心模板记住先排序排序是前提所有区间类题目通用套路。最大子数组53Kadane算法必须背熟连续子数组最优解进阶可以了解分治解法。