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 }
标签:map,2461,nums,Distinct,Subarrays,sum,subarrays,subarray,meet From: https://www.cnblogs.com/cnoodle/p/17565311.html