leetcode
leetcode 2151 ~ 2200
长度为 K 子数组中的最大和

长度为 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且右指针已到达数组末尾,那么不可能再形成大小为k的窗口。因此,不需要继续增加窗口大小。这种情况通常表明数组长度小于k,或者因为重复元素的移除导致无法达到k大小的窗口。
🦆
当窗口大小正好等于k时,为什么要立即移动左指针而不是等到找到一个更大的子数组和后再移动?
当窗口大小正好等于k时,按照题目要求,我们需要计算并更新最大子数组和。移动左指针之后,可以立即开始探索新的可能性,即新的窗口组合。这样做可以确保每一种可能的k长度的子数组都被考虑到,同时保持窗口的动态移动,从而有效地找到最大的子数组和。等待直到找到更大的子数组和再移动左指针将会错过一些潜在的窗口配置,减少了算法的效率。

相关问题