题目描述
leetcode 中等题
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
子数组的长度是 k，且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
示例1：
1
2
3
4
5
6
7
8
9
| 输入：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：
1
2
3
4
5
| 输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。
|
提示：
1
2
| 1 <= k <= nums.length <= 1e5
1 <= nums[i] <= 1e5
|
分析
滑动窗口的时间复杂度只有 O(N)，因为不管嵌套了几次内层循环，左右指针都是单调的从 0 -> (n - 1) 递增，即总共的循环次数只会有 n 次，所以时间复杂度是满足题目的数据范围要求的。
滑动窗口 + Set
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public long maximumSubarraySum(int[] nums, int k) {
Set<Integer> exist = new HashSet<>();
int n = nums.length;
long ans = 0;
long curSum = 0;
for(int i = 0, j = 0; i < n && j < n; j++){
int rightItem = nums[j];
while(exist.contains(rightItem)){
exist.remove(nums[i]);
curSum -= nums[i++];
}
curSum += rightItem;
exist.add(rightItem);
if(exist.size() > k){
exist.remove(nums[i]);
curSum -= nums[i++];
}
if(exist.size() == k){
ans = Math.max(ans, curSum);
}
}
return ans;
}
}
|
- 时间复杂度：O（N）：左右指针单调的从
0->(n - 1) 递增，循环次数总共只会有 n 次
- 空间复杂度：O（K）
滑动窗口 + Map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public long maximumSubarraySum(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
int n = nums.length;
long ans = 0;
long curSum = 0;
for(int j = 0; j <= k - 1; j++){
cnt.put(nums[j], cnt.getOrDefault(nums[j], 0) + 1);
curSum += nums[j];
}
if(cnt.size() == k){
ans = Math.max(ans, curSum);
}
for(int i = 1, j = k; j < n; i++, j++){
curSum -= nums[i - 1];
int value = cnt.get(nums[i - 1]);
if(value == 1){
cnt.remove(nums[i - 1]);
}else{
cnt.put(nums[i - 1], value - 1);
}
curSum += nums[j];
cnt.put(nums[j], cnt.getOrDefault(nums[j], 0) + 1);
if(cnt.size() == k){
ans = Math.max(ans, curSum);
}
}
return ans;
}
}
|