1 最大子数组和
难度：中等
问题描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
思路 - 初见
同样采用前缀和的思路，map中存储和的值和当前坐标，最后用值最大的前缀和减去值最小的前缀和
哈希map存在重复和无法存放问题，采用数组存储，只需存储和，数组下标与题目数组保持一致
存在单数组无法解决问题，单数组单独处理
代码 - 初见
class Solution {
public int maxSubArray(int[] nums) {
// 创建数组存储前缀和
int[] prefixSums = new int[nums.length];
int currentSum = 0;
// 1. 遍历计算前缀和并存入数组
for (int i = 0; i < nums.length; i++) {
currentSum += nums[i];
prefixSums[i] = currentSum;
}
// 2. 初始化为整型的最大值和最小值 (按照要求修改)
int maxPrefix = Integer.MIN_VALUE;
int minPrefix = Integer.MAX_VALUE;
// 3. 遍历前缀和数组找出最大值和最小值
for (int sum : prefixSums) {
if (sum > maxPrefix) {
maxPrefix = sum;
}
if (sum < minPrefix) {
minPrefix = sum;
}
}
// 4. 返回最大前缀和减去最小前缀和
return maxPrefix - minPrefix;
}
}问题和改进
🚩 核心逻辑漏洞
你的代码有一个致命的问题：顺序性丢失。
其中必须满足 j < i（减去的那个前缀和，必须出现在当前前缀和的前面）。
你的逻辑是“全局最大前缀 - 全局最小前缀”，这会导致以下两个错误：
“时光倒流”错误：如果全局最大值出现在全局最小值之前，你的算法会用前面的值减去后面的值，这在数学上是不合法的（相当于子数组的结束位置在开始位置之前）。
反例：
[1, -5]前缀和：
[1, -4]你的逻辑：Max(1) - Min(-4) = 5。但显然最大子数组和是 1。
忽略了初始位置：如果不减去任何东西（从头开始的子数组），相当于减去 0。你的代码如果
minPrefix算出来不是 0，就会出错。
✅ 改进思路：一边遍历，一边减去“当前遇到的最小前缀”
我们需要在遍历的过程中，动态维护一个 “目前为止遇到的最小前缀和”。
对于每一个当前的
currentPrefix，我们计算：潜在最大和 = currentPrefix - minPrefixSoFar这样能保证我们减去的永远是出现在当前位置之前的最小值。
代码 - 改进
class Solution {
public int maxSubArray(int[] nums) {
// 记录当前的前缀和
int currentPrefix = 0;
// 关键点1：minPrefix 初始化为 0
// 代表“什么都不减”，即子数组从下标 0 开始的情况
int minPrefix = 0;
// 结果初始化为极小值，防止由负数组成的数组导致结果错误
int maxResult = Integer.MIN_VALUE;
for (int x : nums) {
currentPrefix += x;
// 1. 核心逻辑：尝试用当前前缀和，减去之前出现过的最小前缀和
// 这保证了计算的一定是合法的子数组
maxResult = Math.max(maxResult, currentPrefix - minPrefix);
// 2. 只有在计算完结果后，才更新最小前缀和
// 这样保证了 minPrefix 永远在 currentPrefix 之前（或者就是初始的0）
minPrefix = Math.min(minPrefix, currentPrefix);
}
return maxResult;
}
}发现
这其中是不是还有一个细节，就是只有最小前缀和小于0时才会记录，大于0时不需要减
我们在寻找“被减数”时，只要它是正的，它就是累赘（会把结果变小）。只有当之前的累积和变成了负数（拖后腿了），我们才需要把它“切掉”（减去它）
🚀 进阶：这就是 Kadane 算法
基于你的这个思路，代码可以写得更简单。我们不再显式维护
minPrefix，而是直接维护一个 “当前的贡献值”。逻辑如下：
如果之前的累加和（
sum）是正的，那它对我有增益，我就留着它，继续往上加。如果之前的累加和是负的（或者 0），它只会拖累我（让我变小），我就直接丢弃它，从当前数字重新开始计算。
这被称为 Kadane算法，是这道题的终极解法。
class Solution {
public int maxSubArray(int[] nums) {
int maxAns = nums[0];
int pre = 0; // 代表“之前的累加和”
for (int x : nums) {
// 你的细节在这里体现：
// 如果 pre > 0，说明前面的积累是正资产，加上它 (pre + x)
// 如果 pre <= 0，说明前面的积累是负债，扔掉它，直接从 x 开始 (x)
pre = Math.max(pre + x, x);
// 记录过程中的最大值
maxAns = Math.max(maxAns, pre);
}
return maxAns;
}
}2 合并区间
难度：中等
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
思路 - 初见
合并规则：区间[a,b],[m,n]中m<=b，合并后的终点取两者最大值，即
Math.max(current.end, next.end);先将数组根据第一个数字排序，遍历，查看下一个数组的第一个数字是否满足拼接条件，要么拼接并记录，要么从下一个开始拼
结果记录采用Array转int[][]
class Solution {
public int[][] merge(int[][] intervals) {
// 1. 边界检查
if (intervals.length == 0) {
return new int[0][0];
}
// 2. 排序：根据每个区间的第一个数字（start）进行升序排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// 使用 ArrayList 存储结果，方便动态添加
List<int[]> result = new ArrayList<>();
// 3. 初始化：取出第一个区间作为当前正在比较的区间 [a, b]
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
// 下一个区间 [m, n]
int[] next = intervals[i];
// 4. 核心判断：如果 next 的起点 m <= current 的终点 b
if (next[0] <= current[1]) {
// 发生重叠，进行合并
// 新的终点是两者终点的最大值：max(b, n)
current[1] = Math.max(current[1], next[1]);
} else {
// 没有重叠，说明 current 已经断开了
// 1. 记录当前合并好的 interval
result.add(current);
// 2. 将 next 更新为新的 current，继续往后找
current = next;
}
}
// 5. 别忘了把最后一个 pending 的 interval 加入结果
result.add(current);
// 6. 结果记录采用 List 转 int[][]
return result.toArray(new int[result.size()][]);
}
}问题和改进
逻辑简化：消除对
current变量的单独维护，也不需要循环结束后再补加最后一次，防止漏掉。
代码 - 改进
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][0];
// 1. 排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> result = new ArrayList<>();
// 2. 遍历
for (int[] interval : intervals) {
// 如果结果集为空，或者当前区间的 start > 结果集最后一个的 end
// 说明没有重叠，直接加入
if (result.isEmpty() || interval[0] > result.get(result.size() - 1)[1]) {
result.add(interval);
} else {
// 有重叠，直接更新结果集最后一个区间的 end
// 此时不需要 add，因为已经在 list 里了
int[] lastInterval = result.get(result.size() - 1);
lastInterval[1] = Math.max(lastInterval[1], interval[1]);
}
}
return result.toArray(new int[result.size()][]);
}
}3 轮转数组
难度：中等
题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: 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:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
思路 - 初见
这个我见过
定义reverse方法，先反转length - k个，再反转后k个数字，最后整个数组反转
代码 - 初见
class Solution {
/**
* 轮转数组
* 核心思路：三次翻转法
* 1. 数组长度为 n，移动 k 位。
* 2. 注意：题目要求是“向右”轮转，意味着最后 k 个元素会跑到最前面。
* 3. 策略：
* - 先反转前半部分 (0 到 n-k-1)
* - 再反转后半部分 (n-k 到 n-1)
* - 最后反转整个数组，即可恢复顺序并完成位置交换
*/
public void rotate(int[] nums, int k) {
int n = nums.length;
// 1. 预处理 k
// 如果 k 大于数组长度，实际上是绕圈圈，取模得到有效移动步数
k %= n;
// 如果 k 为 0，无需移动，直接返回
if (k == 0) return;
// 2. 三步反转逻辑 (基于你的原始思路)
// 第一步：反转前半部分 [1, 2, 3, 4] -> [4, 3, 2, 1]
// 范围：0 到 n - k - 1
reverse(nums, 0, n - k - 1);
// 第二步：反转后半部分 [5, 6, 7] -> [7, 6, 5]
// 范围：n - k 到 n - 1
reverse(nums, n - k, n - 1);
// 当前数组状态：[4, 3, 2, 1, 7, 6, 5]
// 第三步：反转整个数组，恢复内部顺序
// [4, 3, 2, 1, 7, 6, 5] -> [5, 6, 7, 1, 2, 3, 4]
reverse(nums, 0, n - 1);
}
/**
* 双指针反转数组指定区间
*/
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}2 除了自身以外数组的乘积
难度：中等
题目描述
给你一个整数数组 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 <= nums.length <= 105-30 <= nums[i] <= 30输入 保证 数组
answer[i]在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
思路 - 初见
存储每一个元素的前缀乘积和后缀乘积，最后让它俩相乘。
代码 - 初见
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
// 1. 先计算“左侧所有元素的乘积” (前缀乘积)
// answer[i] 表示 i 左边所有元素的乘积
answer[0] = 1; // 第0个元素左边没有数字，视为1
for (int i = 1; i < n; i++) {
answer[i] = nums[i - 1] * answer[i - 1];
}
// 2. 再计算“右侧所有元素的乘积” (后缀乘积)
// 我们不需要开辟新数组，直接用一个变量 R 来记录右边的乘积
int R = 1; // 刚开始右边没有数字，视为1
for (int i = n - 1; i >= 0; i--) {
// 对于索引 i：
// 左边的乘积已经在 answer[i] 里了
// 右边的乘积在变量 R 里
// 直接相乘更新 answer[i]
answer[i] = answer[i] * R;
// 更新 R，把当前 nums[i] 乘进去，供下一个位置 (i-1) 使用
R *= nums[i];
}
return answer;
}
}