做網(wǎng)站如何購買服務(wù)器百度收錄入口
Java解決長度為K子的數(shù)組中的的最大和
01 題目
-
給你一個整數(shù)數(shù)組
nums
和一個整數(shù)k
。請你從nums
中滿足下述條件的全部子數(shù)組中找出最大子數(shù)組和:- 子數(shù)組的長度是
k
,且 - 子數(shù)組中的所有元素 各不相同 。
返回滿足題面要求的最大子數(shù)組和。如果不存在子數(shù)組滿足這些條件,返回
0
。子數(shù)組 是數(shù)組中一段連續(xù)非空的元素序列。
示例 1:
輸入:nums = [1,5,4,2,9,9,9], k = 3 輸出:15 解釋:nums 中長度為 3 的子數(shù)組是: - [1,5,4] 滿足全部條件,和為 10 。 - [5,4,2] 滿足全部條件,和為 11 。 - [4,2,9] 滿足全部條件,和為 15 。 - [2,9,9] 不滿足全部條件,因為元素 9 出現(xiàn)重復(fù)。 - [9,9,9] 不滿足全部條件,因為元素 9 出現(xiàn)重復(fù)。 因為 15 是滿足全部條件的所有子數(shù)組中的最大子數(shù)組和,所以返回 15 。
示例 2:
輸入:nums = [4,4,4], k = 3 輸出:0 解釋:nums 中長度為 3 的子數(shù)組是: - [4,4,4] 不滿足全部條件,因為元素 4 出現(xiàn)重復(fù)。 因為不存在滿足全部條件的子數(shù)組,所以返回 0 。
提示:
1 <= k <= nums.length <= 105
1 <= nums[i] <= 105
- 子數(shù)組的長度是
02 知識點
- 彈窗移動
- 有序數(shù)對map的使用
03 我的題解思路
public class maximumSubarraySum {public static void main(String[] args) {
// 測試數(shù)據(jù)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中,每個值出現(xiàn)的次數(shù)for (int i = 0; i < k; i++) {max+=nums[i];
// 設(shè)置每個值出現(xiàn)的次數(shù),第一次為0+1,之后每出現(xiàn)一次加一map.put(nums[i], map.getOrDefault(nums[i],0)+1);}
// 利用map不會重復(fù),判斷第一次彈窗的元素是否符合條件if(map.size()==k) {rs=max;}
// 接著循環(huán)剩下的元素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]);//獲得新左邊界的出現(xiàn)次數(shù)if(index==1) {map.remove(nums[i-k]);//只出現(xiàn)一次,就直接去掉}else {map.put(nums[i-k], index-1);//出現(xiàn)大于一次,就次數(shù)減一}if(map.size()==k) {//判斷本次彈窗的元素是否符合條件,符合則比較值rs=Math.max(max, rs);}} return rs;}
}