删除子数组的最大得分
难度:
标签:
题目描述
代码结果
运行时间: 201 ms, 内存: 27.3 MB
/*
* 题目思路:
* 使用Java Stream和普通的集合操作实现同样的逻辑。
* 虽然Stream不是最合适的工具,但可以通过组合Stream操作来实现。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
public class SolutionStream {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> set = new HashSet<>();
int[] maxScore = {0};
int[] currentSum = {0};
int[] left = {0};
IntStream.range(0, nums.length).forEach(right -> {
while (set.contains(nums[right])) {
set.remove(nums[left[0]]);
currentSum[0] -= nums[left[0]];
left[0]++;
}
set.add(nums[right]);
currentSum[0] += nums[right];
maxScore[0] = Math.max(maxScore[0], currentSum[0]);
});
return maxScore[0];
}
}
解释
方法:
此题解采用滑动窗口加上哈希表的方法来解决问题。首先通过计算前缀和数组来快速求出任何子数组的和。然后,使用一个哈希表来记录每个元素最后出现的位置。通过遍历数组,利用哈希表来判断当前元素是否已在当前考虑的子数组中出现过。如果出现过,说明当前子数组中已包含重复元素,需要调整滑动窗口的起始位置到重复元素的下一个位置。每次调整后,计算并更新可能的最大子数组和。最后,需要处理边界情况,即当数组遍历完成后,检查最后一个可能的子数组的得分。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法实现中,为什么需要使用前缀和数组来快速获取子数组的和?
▷🦆
哈希表中存储元素最后出现的位置是如何帮助调整滑动窗口的起始位置的?
▷🦆
如果当前元素在哈希表中的记录位置小于当前滑动窗口的起始位置会怎样处理?
▷🦆
算法中如何确保每一次调整滑动窗口后都能得到一个无重复元素的子数组?
▷