请勿第一时间看答案，先自己思考，思考不出来，再看答案
题目描述
给你一个整数数组 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
来感知是否已经被去重。但是这种方案会存在一个耗时问题
，当数据复杂时，会导致执行超时。
一个比较巧妙的思路，就是移动左边界 到重复元素的下一个位置，让其不再参与计算。我们用图示来表达这个思路
10
export function
maximumSubarraySum
(
nums
:
number
[],
k
:
number
)
:
number
{
20
let
right
=
0
,
30
left
=
0
,
40
obj
=
{}
as
any
,
// 数组项的值为 key, 值 为 boolean
50
ans
=
0
,
// 存储最大值
60
res
=
0
// 存储当前窗口的和
70
80
while
(right
<
nums.
length
) {
90
// 如果数组项在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