LeetCode Hot100 普通数组专题题解笔记-开发者社区

总览

本篇包含4道Hot100数组经典题：238.除自身以外数组的乘积、189.轮转数组、56.合并区间、53.最大子数组和。
数组题型高频技巧：前缀/后缀乘积、原地反转、排序贪心、动态规划（Kadane算法）。

238. 除了自身以外数组的乘积

思路

题目限制不能使用除法，核心思路：

构造前缀数组L：L[i]= i位置左侧所有元素乘积
构造后缀数组R：R[i]= i位置右侧所有元素乘积
answer[i] = L[i] * R[i]
进阶优化：可以不额外开辟L、R数组，直接复用输出数组实现O(1)额外空间。

classSolution{publicint[]productExceptSelf(int[]nums){intlength=nums.length;// L[i]：nums[i]左边所有元素乘积int[]L=newint[length];// R[i]：nums[i]右边所有元素乘积int[]R=newint[length];int[]answer=newint[length];// 最左侧元素左边没有数字，初始化为1L[0]=1;for(inti=1;i<length;i++){L[i]=nums[i-1]*L[i-1];}// 最右侧元素右边没有数字，初始化为1R[length-1]=1;for(inti=length-2;i>=0;i--){R[i]=nums[i+1]*R[i+1];}// 当前位置结果 = 左侧乘积 * 右侧乘积for(inti=0;i<length;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){intn=nums.length;int[]newArr=newint[n];// 取模，避免k超过数组长度造成越界k=k%n;for(inti=0;i<n;i++){// i位置元素轮转后新下标：(i + k) % nnewArr[(i+k)%n]=nums[i];}// 将新数组覆盖原数组System.arraycopy(newArr,0,nums,0,n);}}

方法2：原地反转（推荐，进阶要求）

原理：

整体反转整个数组
反转前k个元素
反转后面n-k个元素

classSolution{publicvoidrotate(int[]nums,intk){intn=nums.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(start<end){inttemp=nums[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]);List<int[]>res=newArrayList<>();// 先放入第一个区间作为基准res.add(intervals[0]);for(inti=1;i<intervals.length;i++){// 获取结果集合最后一个区间int[]last=res.get(res.size()-1);// 当前遍历区间int[]cur=intervals[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){intpre=0;// 初始最大值设为第一个元素，兼容全负数数组intmax=nums[0];for(inti=0;i<nums.length;i++){intx=nums[i];// 选择：接上前面子数组 或者 单独以当前元素开头pre=Math.max(x,pre+x);// 更新全局最大和max=Math.max(pre,max);}returnmax;}}