2461-长度为 K 子数组中的最大和

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

• 子数组的长度是 k，且
• 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

示例 1：

**输入：** nums = [1,5,4,2,9,9,9], k = 3
**输出：** 15
**解释：** nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

示例 2：

**输入：** nums = [4,4,4], k = 3
**输出：** 0
**解释：** nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

提示：

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105

Problem: 2461. 长度为 K 子数组中的最大和

注释即思路

[]

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {

        int left = 0,right = 0;
        long max = 0;
        long[] sum = new long[nums.length+1];
        
        // 前缀和用于快速计算 连续数组求和
        for (int i = 0; i < nums.length; i++) {
            sum[i+1] = sum[i] + nums[i];
            max = Math.max(max,nums[i]);
        }
        
        // Hash 记录数值最近出现的位置
        int[] records = new int[(int)max+1];
        max = 0;
        // 用 -1 代表没有出现过
        Arrays.fill(records,-1);

        while (right < nums.length ){

            // 当窗口内元素不满足 k
            if(right - left < k){
                // 获取数值 最近出现的位置
                Integer index = records[nums[right]];
                // 更新当前数值位置
                records[nums[right]] = right++;
                // 如果最近出现位置 就在目前窗口内
                // 改变窗口left，来保证窗口内元素不重复
                if(index >= left){
                    left = index+1;
                }
                continue;
            }

            // 满足 K 记录是否最大值，缩小窗口 left++
            max = Math.max(max,sum[right] - sum[left++]);
        }
        
        // 处理边界
        if(right - left == k)
            max = Math.max(max,sum[right] - sum[left]);

        return max;
    }
}

复杂度

• 时间复杂度:

  添加时间复杂度, 示例： O(n)

• 空间复杂度:

  添加空间复杂度, 示例： O(max（numsValue）+ n)