526互联

[LeetCode] 2461. Maximum Sum of Distinct Subarrays With Length K

发布时间 2023-07-19 13:15:32作者: CNoodle

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

  • The length of the subarray is k, and
  • All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

Constraints:

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

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

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

子数组的长度是 k，且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是滑动窗口。这一题是滑动窗口，窗口尺寸固定为 K。这里我用 hashmap 记录每个不同元素及其出现次数。如果你是用 for 循环来维护窗口的尺寸的话（意思是右指针往前走一步，左指针立马也往前走一步），只能用 hashmap 做。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public long maximumSubarraySum(int[] nums, int k) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         long sum = 0L;
 5         for (int i = 0; i < k; i++) {
 6             sum += nums[i];
 7             map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
 8         }
 9 
10         long res = 0L;
11         if (map.size() == k) {
12             res = sum;
13         }
14 
15         for (int i = k; i < nums.length; i++) {
16             map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
17             sum += nums[i];
18             sum -= nums[i - k];
19             map.put(nums[i - k], map.get(nums[i - k]) - 1);
20             if (map.get(nums[i - k]) == 0) {
21                 map.remove(nums[i - k]);
22             }
23             if (map.size() == k) {
24                 res = Math.max(res, sum);
25             }
26         }
27         return res;
28     }
29 }

 

LeetCode 题目总结