天津网站制作西安微信推广方式有哪些

Java解决长度为K子的数组中的的最大和

01 题目

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

  • 子数组的长度是 k，且
  • 子数组中的所有元素 各不相同 。

  返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

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

  示例 1：

  输入：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：

  输入：nums = [4,4,4], k = 3
  输出：0
  解释：nums 中长度为 3 的子数组是：
  - [4,4,4] 不满足全部条件，因为元素 4 出现重复。
  因为不存在满足全部条件的子数组，所以返回 0 。
  

  提示：

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

02 知识点

• 弹窗移动
• 有序数对map的使用

03 我的题解思路

public class maximumSubarraySum {public static void main(String[] args) {
//		测试数据int[] nums= {1,1,1,7,8,9};System.out.println(maximumSubarraySum(nums, 3));}public static long maximumSubarraySum(int[] nums, int k) {long rs=0;//最终返回的答案long max=0;//局部最大值Map<Integer, Integer> map=new HashMap<>();
//			 弹窗最开始，记录0到k中，每个值出现的次数for (int i = 0; i < k; i++) {max+=nums[i];
//				 设置每个值出现的次数，第一次为0+1，之后每出现一次加一map.put(nums[i], map.getOrDefault(nums[i],0)+1);}
//			 利用map不会重复，判断第一次弹窗的元素是否符合条件if(map.size()==k) {rs=max;}
//			 接着循环剩下的元素for (int i = k; i < nums.length; i++) {
//				 整个弹窗向右移动max+=nums[i];//弹窗右边移动map.put(nums[i], map.getOrDefault(nums[i],0)+1);//记录新右边界的值max-=nums[i-k];//弹窗左边移动int index=map.get(nums[i-k]);//获得新左边界的出现次数if(index==1) {map.remove(nums[i-k]);//只出现一次，就直接去掉}else {map.put(nums[i-k], index-1);//出现大于一次，就次数减一}if(map.size()==k) {//判断本次弹窗的元素是否符合条件，符合则比较值rs=Math.max(max, rs);}} return rs;}
}