题目描述

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

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

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

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

题目解析

本题主要涉及到的知识点有：

• while 循环 / for 循环
• 双指针
• 滑动窗口

这里比较麻烦的是, 我们应该如何判断当前的子数组中, 是否存在重复的元素. 当然, 我们可以很轻松的将子数组进行去重处理, 但是, 如何做才能得到更少的时间消耗是一个需要认真思考的问题.

这里最主要的就是, 滑动窗口的技巧. 分享一下我的解法, 可以做到最短时间最低内存消耗

首先, 我们定义一个普通的 Object 对象, 用来存储当前元素是否已经存在.

例如, 针对数组 [1, 2, 3, 4] , 我们可以定义如下的对象

1
const map = {
2
  1: true,
3
  2: true,
4
  3: true,
5
  4: true
6
}

在指针滑动的过程中, 我们需要确保只有子数组中的元素作为 key , 对应的值才能等于 true, 如果当前元素不在窗口范围中了, 那么就应该将其 key 对应的值设置为 false

这样, 我们就可以很方便的判断出, 新进入窗口的元素, 是否已经存在于窗口中了.

1
if (map(newNum)) {
2
  // 新元素已经存在于窗口中
3
}

接下来, 就是另外一个很重要的技巧. 当我们发现当前元素已经存在于窗口中了, 那么我们应该如何移动左指针呢？如何去重呢？

一个比较常规的思路就是通过 slice 等方法明确得到当前窗口的所有元素, 然后通过 Set 等方法去重, 通过判断 length 来感知是否已经被去重. 但是这种方案会存在一个耗时问题, 当数据复杂时, 会导致执行超时.

一个比较巧妙的思路, 就是移动左边界到重复元素的下一个位置, 让其不再参与计算. 我们用图示来表达这个思路

01
export function maximumSubarraySum(nums: number[], k: number): number {
02
  let right = 0, 
03
      left = 0, 
04
      obj = {} as any, // 数组项的值为 key, 值 为 boolean
05
      ans = 0, // 存储最大值
06
      res = 0 // 存储当前窗口的和
07

08
  while (right < nums.length) {
09
    // 如果数组项在obj中存在  移动 left 指针, 并将对应的值设置为false, 直到没有重复项
10
    while (obj[nums[right]]) {
11
      obj[nums[left]] = false
12
      res -= nums[left++]
13
    }
14
    
15
    // 将当前值存入 obj 中, 并将其值设置为 true, 表示该值已经出现过一次
16
    obj[nums[right]] = true
17
    res += nums[right++]
18

19
    // 如果有k个了 取大值, 计算好最大值之后, 移动一次 left 指针, 让窗口继续往右边滑动
20
    if (right - left === k) {
21
      ans = Math.max(ans, res)
22
      obj[nums[left]] = false
23
      res -= nums[left++]
24
    }
25
  }
26
  return ans
27
};

原题地址：leetcode 2461