普通数组
难度说明：🟢简单🟡中等🔴困难
普通数组
🟡01-最大子数组和（53）
1.题目内容
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
子数组：是数组中的一个连续部分
2.题解思路
❌方法1：暴力循环（超时）
本题思路和"子串"题型中的【和为K的子数组】这一题目类似，可以通过双层循环暴力遍历的方式实现。但是需注意对初始结果的处理
因为此处是在遍历过程中更新最大值，这个最大值可能是负数，如果只是单纯和res（初始为0）进行比较就会导致忽略了最大值为负数的情况。硬核一点就是将res设置为无限小（Integer.MIN_VALUE）
/**
* 53.最大子数组和
*/
public class Solution {
/**
* 暴力双层循环：外层敲定起点、内层敲定终点
*/
public int maxSubArray(int[] nums) {
// 定义结果
// int res = -999999999;
int res = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int currentCount = 0;
// 内存循环敲定终点，通过累加获取最大值
for(int j=i;j<nums.length;j++){
currentCount += nums[j];
// 更新最大值（此处需区分整数和负数的情况，因为res初始化为0）
res = Math.max(res,currentCount);
}
}
// 返回结果
return res;
}
public static void main(String[] args) {
// 可能存在问题：初始化了res为0，忽略了可能存在负数的情况，导致一些边界没有覆盖到
int[] nums = {-1};
Solution solution = new Solution();
System.out.println(solution.maxSubArray(nums)); // 理论返回-1，但是如果没有处理res就会返回0
}
}
复杂度分析
- 时间复杂度：
- 空间复杂度：
✨方法2：动态规划
求解对象：最优化问题（最大、最小值），将问题分为规模逐渐减小的子问题，子问题是互相重复的
用例分析：【-2,1,3,4,-1,2,1,-5,4】，基于题目分析，此处是为了找出一个连续最大的子序列，最暴力的做法就是获取所有的连续子序列，依次对比最大值，因此最初的暴力解法是三层遍历，然后进一步优化演进为上述的两层遍历+累加优化。
基于动态规划的方向思考，可以将上述的组合先分解成9个小组的组合（按照以每个元素结尾的连续序列概念进行划分）：
- 子组合1：以第1个数字
-2结尾的连续序列=》-2=》MAX为-2 - 子组合2：以第2个数字
1结尾的连续序列=》-2,1、1=》MAX为1 - 子组合3：以第3个数字
3结尾的连续序列=》-2,1,3、1,3、3=》MAX为4 - 子组合4：以第4个数字
4结尾的连续序列=》-2,1,3,4、1,3,4、3,4、4=》MAX为7 - ...... 以此类推 ......
如果可以得到每一个子组合的最优解（即子序列最大值），那么整体的最大值就可以通过对比这9个子组合的最大值获取到，这是"最优子问题"的思考
继续拆解组合规律，可以看到每个组合的序列都是在上一个组合的基础上添加当前元素（以组合2和组合3为例，组合3的连续序列构成是在组合2的基础上加上当前元素3包括其本身），可以据此得到组合之间的关系。此处的关心重点并不是这个序列如何生成的，而是最大值之间的关系
子组合的序列可以分为两部分，一部分是通过继承i-1组合加上当前元素得到的序列，一部分是其本身就是一个序列。即子组合3可以看做两部分组成：
- ①子组合2的连续序列+元素本身：
-2,1+3=》-2,1,3、1+3=》1,3（最大值为子组合2的最大值+当前元素，即1+3=4，此处需要关注的是前一个子组合的最大值是否可以带来正增益，如果不行则可以直接抛弃） - ②元素本身：
3
因此对于子组合3而言，其最大值为①②中的最大值=》4
/**
* 53.最大子数组和
* 动态规划
*/
public class Solution2 {
public int maxSubArray(int[] nums) {
// 定义结果
int res = nums[0];
// 定义当前最大值
int currentMax = nums[0];
// 单层循环
for (int i = 1; i < nums.length; i++) {
// 获取当前子组合的最大值（当前子组合的最大值被拆解为两部分：上一个子组合的最大值+num[i]、其自身num[i]）
currentMax = Math.max(nums[i], currentMax + nums[i]);
// 更新最大值
res = Math.max(res, currentMax);
}
// 返回结果
return res;
}
}
3.复盘
🟡02-合并区间（56）
1.题目内容
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
2.题解思路
👻方法1：二维数组遍历
思路分析
先对intervals二维数组进行排序，根据intervals[i][0]进行排序（即每个子数组的首元素进行排序），假设得到{[1, 10], [2, 5], [3, 11], [13, 14]}，基于此遍历排序后的数组，然后判断是否要进行区间合并
[1,10]与[2,5]：比较10与2、5，因为10>2、10>5（x>left && x>right），所以合并后的区间[1,10]继续将新得到的区间与后面的进行比较：
[1,10]与[3,11]，因为10>3、10<11（x>left && x<right），所以合并后的区间[1,11]以此类推，
[1,11]与[13,14]，因为11<13（x<left），无法合并，因此更新后的新区间为{[1,11],[13,14]}，相应的下次比较应该是[13,14]与其他区间比较算法实现核心
- 先将二维数组进行排序（按照每个数组的首元素进行排序），然后遍历排序后的二维数组（可以使用
Arrays.sort搭配Lambda表达式进行排序） - 定义一个区间索引（left、right）初始化为
(intervals[0],intervals[1])，由它负责与待合并区间（vl、vr）进行比较- 如果right>vl，说明两个区间有重叠部分，需进一步比较right和vr的值来更新索引
- 如果right<vr，则需更新右区间（
[1,10],[2,13]这种情况） - 如果right>vr，则不需要更新区间（
[1,10],[2,5]这种情况）
- 如果right<vr，则需更新右区间（
- 如果right<vl，说明两个区间没有重叠部分，需要将当前比较的区间加入结果集，并更新区间索引位置
- 即
[1,10],[13,15]这种情况，需要将[13,15]加入结果集，并且当前的left、right索引应该对应更新为[13,15]
- 即
- 遍历完成，最后需要将这个（left、right）加入结果集（它表示的是每次比较合并的最新区间）
- 如果right>vl，说明两个区间有重叠部分，需进一步比较right和vr的值来更新索引
- 先将二维数组进行排序（按照每个数组的首元素进行排序），然后遍历排序后的二维数组（可以使用
/**
* 56.合并区间
*/
public class Solution {
public int[][] merge(int[][] intervals) {
// 定义结果集
List<int[]> list = new ArrayList<int[]>();
// 根据每个子数组的首元素对数组进行排序(可以用Lambda表达式简化)
/*
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
*/
Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
// 定义区间的左右指针，从第一个数组开始（left左区间、right右区间）
int left = intervals[0][0];
int right = intervals[0][1];
// 循环遍历排序后的数组元素，将右区间和对应区间的左右(nl\nr)进行对比
for(int i=1;i<intervals.length;i++){
// 如果right>nl 说明区间重叠，需要更新区间
if(right>=intervals[i][0]){
if(right>=intervals[i][1]){
// right > nr,说明是[1,10] [2,3]这种情况，不需要更新区间
}else{
// right < nr,说明时[1,10] [2,12]这种情况，需要更新右区间
right=intervals[i][1];
}
}else{
// 如果right<nl 说明区间无重叠，需要将区间结果集，并更新当前指针索引
list.add(new int[]{left,right});
left=intervals[i][0];
right=intervals[i][1];
}
}
// 将当前指针索引区间加入结果集
list.add(new int[]{left,right});
// 返回结果集
return list.toArray(new int[list.size()][]);
}
}
复杂度分析
- 时间复杂度：
- 空间复杂度：
3.复盘
🟡03-轮转数组（189）
1.题目内容
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
2.题解思路
👻方法1：反转法
以【1 2 3 4 5 6 7】为例，假设k为3，可以将这个轮转拆分为3个步骤：
- 反转整个数组：【7 6 5 4 3 2 1】
- 反转前K（3）个数据：【5 6 7 4 3 2 1】
- 反转后n-k（4）个数据：【5 6 7 1 2 3 4】
针对n和k的值，由于没有设定k小于n，因此要考虑"轮次"问题，因为轮转n次相当于没有轮转，轮转n+1次相当于轮转n次，因此此处轮转k次等价于轮转k%n次
基于此思路，则可借助List进行操作，通过Collections提供的reverse方法进行操作
public void rotate(int[] nums, int k) {
// 定义结果集（将数组转为List）
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
// 计算反转轮次
k = k % nums.length;
// 反转整个数组
Collections.reverse(list);
// 反转前K个数据
Collections.reverse(list.subList(0, k));
// 反转后N-K个数据
Collections.reverse(list.subList(k, list.size()));
// 输出结果
for (int i = 0; i < list.size(); i++) {
nums[i] = list.get(i);
}
}
复杂度分析
- 时间复杂度：
- 空间复杂度：
3.复盘
04-除自身以外数组的乘积（238）
1.题目内容
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题
示例 1:
输入: nums = [1,2,3,4] 输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
2.题解思路
❌方法1：暴力循环（超时）
暴力循环：双层循环数组，外层循环敲定元素i，内层循环敲定除了i本身的所有数的累乘操作
/**
* 238.除自身以外数组的乘积
* 思路：暴力循环（双层循环）
*/
public class Solution1 {
public int[] productExceptSelf(int[] nums) {
// 定义结果
int[] res = new int[nums.length];
// 暴力双层循环，外层循环敲定指定元素，内存循坏做除自身外的累乘操作
for (int i=0;i<nums.length;i++) {
res[i] = 1; // 1乘以任何数都等于本身
for(int j=0;j<nums.length;j++){
if(i!=j){
// 排除自身进行累乘操作
res[i] *= nums[j];
}
}
}
// 返回结果
return res;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4};
Solution1 solution = new Solution1();
System.out.println(solution.productExceptSelf(nums));
}
}
复杂度分析
- 时间复杂度：
- 空间复杂度：
✨方法2：左右乘积法
思路：分别计算元素i左右两侧的乘积，然后最后做相乘操作，以1 2 3 4 5为例进行分析
- 左侧乘积：定义
int[] left结果集存放左侧累乘结果**（从左到右填充）**left[0]首位左侧没有数字，初始化为1（1乘以任何数都为本身）left[1] = left[0] * nums[0]、left[2] = left[1] * nums[1]（遍历、累乘操作从下标1开始）
- 右侧乘积：定义
int[] right结果集存放右侧累乘结果（与左侧相反，右侧需要从数组尾部开始）（从右到左填充）right[nums.length-1]最后一个元素的右侧没有数字，初始化为1- 遍历起始位置从右侧的下一位开始，因此start为nums.length-2的位置，
right[i]=right[i+1]*num[i+1]
- 处理乘积：循环遍历数组进行相乘
public class Solution2 {
public int[] productExceptSelf(int[] nums) {
// 定义变量存放数组长度
int n = nums.length;
// 定义结果
int[] res = new int[n];
// 分别定义数据用于存放当前i位置的左侧累乘、右侧累乘结果
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];
System.out.println(res[i]);
}
// 右侧累乘操作(从尾部开始)
right[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
// 左右乘积相乘得到结果
for (int i = 0; i < n; i++) {
res[i] = left[i] * right[i];
}
// 返回结果
return res;
}
}
为了进一步节省空间占用和遍历操作，可以先进行左侧累乘，然后在右侧累乘的过程中直接计算得到i位置的内容
/**
* 238.除自身以外数组的乘积
* 思路：左右乘积（进阶）
*/
public class Solution3 {
public int[] productExceptSelf(int[] nums) {
// 定义结果
int[] res = new int[nums.length];
/**
* 填充结果集为累乘结果(1 2 3 4)
* res[1]=res[0]*nums[0]= 1 * 1 = 1
* res[2]=res[1]*nums[1]= 1 * 2 =2
* res[3]=res[2]*nums[2]= 2 * 3 =6
* ......
*/
// 填充左侧乘积结果
res[0] = 1;
for (int i = 1; i < nums.length; i++) {
res[i] = res[i - 1] * nums[i - 1];
System.out.println(res[i]);
}
// 填充右侧乘积（右侧乘积是从尾部开始遍历）
int right = 1; // 定义右侧的累乘值
for(int i=nums.length-1; i>=0; i--) {
// 进行结果累乘
res[i] *= right;
// 更新right
right *= nums[i];
}
// 返回结果
return res;
}
}