这里记录刷hot100的思考过程详解，方便后续记忆复习。
题号53
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
具体题解
class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
int currentmax=0;
for(int num:nums){
currentmax+=num;
max=Math.max(max,currentmax);
if(currentmax<0){
currentmax=0;
}
}
return max;
}
}
思路解析
每当序列和为0或小于0时，就将下一个数作为新序列起点。需要将“判断当前最大max”放在判断currentmax之前，来解决都是负数的情况。
必会知识
无
题号56
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
具体题解
class Solution {
public int[][] merge(int[][] intervals) {
int len=intervals.length;
if(len==0){
return new int[0][2];
}
Arrays.sort(intervals,new Comparator<int []>(){
@Override
public int compare(int[] arr1,int[] arr2){
return arr1[0]-arr2[0];
}
});
List<int[]> merged=new ArrayList<>();
for(int i=0;i<intervals.length;i++){
int l=intervals[i][0];
int r=intervals[i][1];
if(merged.isEmpty()||merged.get(merged.size()-1)[1]<l){
merged.add(new int[]{l,r});
}else{
merged.get(merged.size()-1)[1]=Math.max(merged.get(merged.size()-1)[1],r);
}
}
return merged.toArray(new int[merged.size()][2]);
}
}
思路解析
将二维数组安装第一个自定义排序，从小到大。比较边界值后list集合合并结果。
必会知识
1.Arrays.sort自定义排序
2.集合转数组，merged.toArray（）
题号189
189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
具体题解
class Solution {
public void rotate(int[] nums, int k) {
int len=nums.length;
int[] tmp=new int[len];
if(k>len){
k=k%len;
}
for(int i=0;i<len;i++){
tmp[i]=nums[(len-k+i)%len];
}
System.arraycopy(tmp,0,nums,0,len);
}
}
思路解析
通过计算公式复制到第二个数组上。
必会知识
System.arraycopy()复制数组
题号238
238. 除了自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
具体题解
class Solution {
public int[] productExceptSelf(int[] nums) {
int len=nums.length;
int[] L=new int[len];
int[] R=new int[len];
int[] ans=new int[len];
L[0]=1;
R[len-1]=1;
for(int i=1;i<len;i++){
L[i]=L[i-1]*nums[i-1];
}
for(int i=len-2;i>=0;i–){
R[i]=R[i+1]*nums[i+1];
}
for(int i=0;i<len;i++){
ans[i]=L[i]*R[i];
}
return ans;
}
}
思路解析
分别计算左右数的和，再合起来算最终结果
必会知识
无
题号41
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
具体题解
class Solution {
public int firstMissingPositive(int[] nums) {
int len=nums.length;
for(int i=0;i<len;i++){
if(nums[i]<=0){
nums[i]=len+1;
}
}
for(int i=0;i<len;i++){
int num=Math.abs(nums[i]);
if(num<=len){
nums[num-1]=-1*Math.abs(nums[num-1]);
}
}
for(int i=0;i<len;i++){
if(nums[i]>0){
return i+1;
}
}
return len+1;
}
}
思路解析
所求数一定在1~n+1之内。这里先将负数赋为n+1排除影响，然后将在1~n之内的数对应的下标赋值为负数，且该负数是原先数的相反数。最终某下标对应数仍为正数则没有出现过。
必会知识
无
