Day8--滑动窗口与双指针--1004. 最大连续1的个数 III，1658. 将 x 减到 0 的最小操作数，3641. 最长半重复子数组

思路【我】：

题意：窗口中最多有k个0

不定长滑动窗口三步曲：入–出–更新

class Solution {public int longestOnes(int[] nums, int k) {// 题意：窗口中最多有k个0int n = nums.length;int zero = 0;int left = 0;int maxLen = 0;for (int i = 0; i < n; i++) {// 1，入if (nums[i] == 0) {zero++;}// 2，出while (zero > k) {if (nums[left] == 0) {zero--;}left++;}// 3，更新maxLen = Math.max(maxLen, i - left + 1);}return maxLen;}
}

附加题：顺便把这两题也做了吧，几乎是复制过去就能提交。487. 最大连续1的个数 II和485. 最大连续 1 的个数。

思路【灵艾山茶府】：

逆向思维：要选头尾的元素相加等于x，也就是中间的元素相加等于total-x。

要使头尾相加的元素最少，也就是中间的窗口尽量长——也就是求多大的窗口可以累计和为total-x

1. 使用Arrays.stream(nums).sum()求和，记为total
   • 如果x比total还大，没办法，返回-1
   • 要求的total-x定义为need。如果need==0，答案就是要把整个数组都删掉（这里要单独讨论，否则need为0，就求不到窗口了）
2. 不定长滑动窗口三步曲：入–出–更新
   1. 入
   2. 出
   3. 更新（注意不能一找到need==sum就返回，要找最大的窗口）
3. 如果maxLen有值（不再为0），也就是中间窗口能凑成need，就是有恰好。否则就是凑不成，返回-1。

class Solution {public int minOperations(int[] nums, int x) {int n = nums.length;// 思路：逆向思维：要选头尾的元素相加等于x，也就是中间的元素相加等于total-x// 要使头尾相加的元素最少，也就是中间的窗口尽量长——也就是求多大的窗口可以累计和为total-x// 使用Arrays.stream(nums).sum()求和int total = Arrays.stream(nums).sum();// 如果x比total还大，没办法，返回-1if (x > total) {return -1;}// 要求的total-x定义为needint need = total - x;// 如果need==0，答案就是要把整个数组都删掉（这里要单独讨论，否则need为0，就求不到窗口了）if (need == 0) {return n;}// 初始化int left = 0;int maxLen = 0;int sum = 0;// 开始滑动窗口for (int i = 0; i < n; i++) {// 1，入sum += nums[i];// 2，出while (left < n && sum > need) {sum -= nums[left];left++;}// 3，更新（注意不能一找到need==sum就返回，要找最大的窗口）if (sum == need) {maxLen = Math.max(maxLen, i - left + 1);}}// 如果maxLen有值，也就是中间窗口能凑成need，就是有恰好。否则就是凑不成，返回-1return maxLen != 0 ? n - maxLen : -1;}
}

简洁版：

class Solution {public int minOperations(int[] nums, int x) {int n = nums.length;int total = Arrays.stream(nums).sum();if (x > total) {return -1;}int need = total - x;if (need == 0) {return n;}int left = 0;int maxLen = 0;int sum = 0;for (int i = 0; i < n; i++) {sum += nums[i];while (left < n && sum > need) {sum -= nums[left];left++;}if (sum == need) {maxLen = Math.max(maxLen, i - left + 1);}}return maxLen != 0 ? n - maxLen : -1;}
}

思路【我】：

1. 利用map记录窗口内各个元素出现的次数。

2. 利用set<元素>，记录窗口内，出现次数>1，也就是“重复”的元素

3. 不定长滑动窗口三步曲：入–出–更新。

   1. 入。如果同一个元素数量大于1（重复），加入到set
   2. 出。如果set的元素，大于k个，不符合窗口要求，收缩窗口直到窗口合法
      • 减到为0的不用管，只需要关注原来大于1（重复）的元素，现在减到1了，就是不重复了
   3. 更新maxLen

class Solution {public int longestSubarray(int[] nums, int k) {int n = nums.length;int left = 0;int maxLen = 0;int[] map = new int[100001];Set<Integer> set = new HashSet<>();// 开始滑动窗口for (int i = 0; i < n; i++) {// 1，入。如果同一个元素数量大于1（重复），加入到setif (++map[nums[i]] > 1) {set.add(nums[i]);}// 2，出。如果set的元素，大于k个，不符合窗口要求，收缩窗口直到窗口合法while (set.size() > k) {// 减到为0的不用管，只需要关注原来大于1（重复）的元素，现在减到1了，就是不重复了if (--map[nums[left]] == 1) {set.remove(nums[left]);}left++;}// 3，更新maxLen = Math.max(maxLen, i - left + 1);}return maxLen;}
}

使用map<元素，出现次数>的版本：

class Solution {public int longestSubarray(int[] nums, int k) {int n = nums.length;int left = 0;int maxLen = 0;Map<Integer, Integer> map = new HashMap<>();Set<Integer> set = new HashSet<>();for (int i = 0; i < n; i++) {// merge(1)会返回操作后，该key对应的valueif (map.merge(nums[i], 1, Integer::sum) > 1) {set.add(nums[i]);}while (set.size() > k) {if (map.merge(nums[left], -1, Integer::sum) == 1) {set.remove(nums[left]);}left++;}maxLen = Math.max(maxLen, i - left + 1);}return maxLen;}
}