第 173 场双周赛Q2——3795. 不同元素和至少为 K 的最短子数组长度

题目链接：3795. 不同元素和至少为 K 的最短子数组长度（中等）

算法原理：

解法：滑动窗口

146ms击败35.92%

时间复杂度O(N)

系统滑动窗口专题👇

一轮复习——C.滑动窗口模型总结

本题的滑动窗口模型为不定长-求长度-越长越合法/求最短/最小

①进窗口：用哈希表记录，保证相同值只加一次

②出窗口：总和>=k就持续出窗口

③更新：在出窗口时，也就是不断缩小范围时更新

Java代码：

class Solution { public int minLength(int[] nums, int k) { //滑动窗口 Map<Integer,Integer> hash=new HashMap<>(); int n=nums.length,sum=0,ret=0x3f3f3f3f; for(int left=0,right=0;right<n;right++){ //相同值只加一次 if(!hash.containsKey(nums[right])) sum+=nums[right]; //进窗口 hash.put(nums[right],hash.getOrDefault(nums[right],0)+1); //出窗口 while(sum>=k){ //更新:出窗口时不断缩小范围更新 if(sum>=k) ret=Math.min(ret,right-left+1); hash.put(nums[left],hash.get(nums[left])-1); if(hash.get(nums[left])==0){ sum-=nums[left]; hash.remove(nums[left]); } left++; } } return ret==0x3f3f3f3f?-1:ret; } }