首页 > 其他分享 >[LeetCode] 2461. Maximum Sum of Distinct Subarrays With Length K

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

时间:2023-07-19 13:23:08浏览次数:52  
标签:map 2461 nums Distinct Subarrays sum subarrays subarray meet

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.

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 题目总结

标签:map,2461,nums,Distinct,Subarrays,sum,subarrays,subarray,meet
From: https://www.cnblogs.com/cnoodle/p/17565311.html

相关文章

  • Codeforces 293B Distinct Paths
    发现\(n,m\)的数据范围是假的,因为每一步一个颜色最多也就\(k\le10\)种颜色,所以当\(n+m-1>k\)时一定无解。接下来发现这个数据范围挺小的,考虑状压,设\(f_{x,y}\)为走到\((x,y)\)点所用的颜色的集合,其可以由\(f_{x-1,y},f_{x,y-1}\)推来。然后就可以......
  • 100W数据去重,用distinct还是group by
    京东太狠:100W数据去重,用distinct还是groupby,说说理由?原创 40岁老架构师尼恩 技术自由圈 2023-06-0411:37 发表于广东收录于合集#面试题86个技术自由圈疯狂创客圈(技术自由架构圈):一个技术狂人、技术大神、高性能发烧友圈子。圈内一大波顶级高手、架构师、......
  • DistinctAdjacent
    [ABC307E]DistinctAdjacent解答1:我们将圆环上有\(i\)个人的情况的答案记为\(f(i)\)。考虑有\(i+1\)个人排成一排的情况,此时答案为\(M\times(M-1)^i\)。这样的传递方式中,如果是圆环的情况且不满足条件的传递方式只有人\(i+1\)和人\(1\)的情况不同。因此,这两个人可......
  • SQL中的distinct的使用方法
    1.distinct含义与使用方法distinct用来查询不重复记录的条数,即用distinct来返回不重复字段的条数(count(distinctid)),其原因是distinct只能返回他的目标字段,而无法返回其他字段。注意事项distinct【查询字段】,必须放在要查询字段的开头,即放在第一个参数;只能在SELECT语句中使......
  • MySQL 8 如何解决快速获取数据库中所有业务库表列的distinct 值,不使用SQL
    开头还是介绍一下群,如果感兴趣polardb,mongodb,mysql,postgresql,redis等有问题,有需求都可以加群群内有各大数据库行业大咖,CTO,可以解决你的问题。最近我们接到一个需求,在数据库内,无准确目标的寻找每个表中的字里面包含某些特殊字符的列。工作了快半辈子了,也是第一次听说这样......
  • 京东太狠:100W数据去重,用distinct还是group by,说说理由?
    文章很长,且持续更新,建议收藏起来,慢慢读!疯狂创客圈总目录博客园版为您奉上珍贵的学习资源:免费赠送:《尼恩Java面试宝典》持续更新+史上最全+面试必备2000页+面试必备+大厂必备+涨薪必备免费赠送:《尼恩技术圣经+高并发系列PDF》,帮你实现技术自由,完成职业升级,薪......
  • 【转载】Mybatis Plus QueryWrapper结合lambda表达式使用distinct的方法
    MybatisPlusQueryWrapper的lambda用起来感觉挺爽的,有点JPA的感觉,也不需要拼很多字符串,可以利用IDE的代码检查功能,总之好处多多,停不下来。最近遇到一个问题,需要对SQL查询的结果做去重处理,自然想到了使用distinct。对于复杂的SQL语句,一般使用自定义XML的方式,但是这么个小问题,XML......
  • ShardingSphere + Pagehelper 组合sql查询中包含 DISTINCT GROUP BY 等关键字和聚合函
    Pagehelper中配置说明params:为了支持startPage(Objectparams)方法,增加了该参数来配置参数映射,用于从对象中根据属性名取值,可以配置 pageNum,pageSize,count,pageSizeZero,reasonable,不配置映射的用默认值,默认值为pageNum=pageNum;pageSize=pageSize;count=countSql;r......
  • sql语法--distinct去重
      distinct对单列数据实现去重效果并返回单列如果是对多列去重,当且仅当多条数据中多列的数据完全一致才能够去重如图1selectdistinctpassword,phonefromtb_user; 图1 不能够去重如图2 ......
  • abc252_d Distinct Trio 题解
    这是数学题耶!题意给定一个整数\(n\)和一个长度为\(n\)的整数序列\(a\),求满足以下要求的三元组个数:\(1\leqslanti<j<k\leqslantn\)。\(a_i\nea_j\),\(a_j\nea_k\),\(a_k\nea_i\)。思路先想正着做,好,不会。正着做不行就反着做,先算出所有情况,再去掉不合法。......