长度为 K 子数组中的最大和
难度:
标签:
题目描述
代码结果
运行时间: 130 ms, 内存: 32.4 MB
import java.util.HashSet;
import java.util.stream.IntStream;
/**
* 题目思路:
* 1. 使用IntStream遍历数组索引,滑动窗口大小为k。
* 2. 对每个窗口,使用HashSet检查元素是否各不相同。
* 3. 计算满足条件的子数组的和,并使用Stream的max方法记录最大值。
*/
public class Solution {
public int maximumSubarraySum(int[] nums, int k) {
int n = nums.length;
if (n < k) return 0;
return IntStream.rangeClosed(0, n - k)
.map(i -> {
HashSet<Integer> set = new HashSet<>();
int currentSum = 0;
for (int j = i; j < i + k; j++) {
if (set.contains(nums[j])) {
return 0;
}
set.add(nums[j]);
currentSum += nums[j];
}
return currentSum;
})
.max()
.orElse(0);
}
}
解释
方法:
题解采用了滑动窗口的策略来求解问题。首先,维护一个当前窗口内的元素集合(window)和窗口内元素的和(curr_sum)。通过双指针技术,右指针(right)遍历整个数组,将每个元素加入窗口。如果遇到窗口内已存在的元素(即有重复),则左指针(left)移动,并相应地从集合和当前和中移除左指针指向的元素,直到窗口内没有重复元素。每当窗口大小达到k时,比较当前窗口和(curr_sum)与历史最大和(max_sum),并更新最大和。之后,移动左指针缩小窗口,继续检查后续的可能窗口。通过这种方式,可以有效地找到所有满足条件的子数组,并计算出最大的子数组和。
时间复杂度:
O(n)
空间复杂度:
O(k)
代码细节讲解
🦆
为什么在滑动窗口策略中,当窗口内出现重复元素时,只移动左指针而不是右指针?
▷🦆
在代码中,如果窗口的大小一直小于k,是否有必要继续增加窗口的大小,即使右指针已经到达数组的末尾?
▷🦆
当窗口大小正好等于k时,为什么要立即移动左指针而不是等到找到一个更大的子数组和后再移动?
▷