滑動窗口

要區(qū)分最小和最大滑窗，內層while循環(huán)的條件和更新結果的地方

核心：

關鍵的區(qū)別在于，最大滑窗是在迭代右移右邊界的過程中更新結果，而最小滑窗是在迭代右移左邊界的過程中更新結果。

最小滑窗

給定數(shù)組 nums，定義滑窗的左右邊界 i, j，求滿足某個條件的滑窗的最小長度。

while j < len(nums)://這個while也可用fori代替判斷[i, j]是否滿足條件while 滿足條件：不斷更新結果(注意在while內更新！)i += 1 （最大程度的壓縮i，使得滑窗盡可能的小）j += 1

L209長度最小的子數(shù)組

• 題目：給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0。

  示例：

  輸入：s = 7, nums = [2,3,1,2,4,3] 輸出：2 解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

  提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

• 

• class Solution {// 滑動窗口public int minSubArrayLen(int s, int[] nums) {int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];//這里要求的是最小子數(shù)組，所以這里的while是滿足條件的//然后在while里面最大程度的壓縮i（也就是左邊界）while (sum >= s) {result = Math.min(result, right - left + 1);sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
  }
  

最大滑窗

給定數(shù)組 nums，定義滑窗的左右邊界 i, j，求滿足某個條件的滑窗的最大長度。

while j < len(nums):判斷[i, j]是否滿足條件while 不滿足條件：i += 1 （最保守的壓縮i，一旦滿足條件了就退出壓縮i的過程，使得滑窗盡可能的大）不斷更新結果（注意在while外更新！）j += 1

L904水果成藍

• 你正在探訪一家農場，農場從左到右種植了一排果樹。這些樹用一個整數(shù)數(shù)組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果 種類 。

  你想要盡可能多地收集水果。然而，農場的主人設定了一些嚴格的規(guī)矩，你必須按照要求采摘水果：

  你只有 兩個 籃子，并且每個籃子只能裝 單一類型 的水果。每個籃子能夠裝的水果總量沒有限制。
  你可以選擇任意一棵樹開始采摘，你必須從 每棵 樹（包括開始采摘的樹）上 恰好摘一個水果 。采摘的水果應當符合籃子中的水果類型。每采摘一次，你將會向右移動到下一棵樹，并繼續(xù)采摘。
  一旦你走到某棵樹前，但水果不符合籃子的水果類型，那么就必須停止采摘。
  給你一個整數(shù)數(shù)組 fruits ，返回你可以收集的水果的 最大 數(shù)目。

• 白話題目：求只包含兩種元素的最長連續(xù)子序列

• class Solution {public int totalFruit(int[] fruits) {int n = fruits.length;Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();int left = 0, ans = 0;for (int right = 0; right < n; ++right) {cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);//注意這里的while是不滿足條件的//并且這里統(tǒng)計的ans是在while外面進行更新的！！！！！//這個與上面的最小子數(shù)組有著本質區(qū)別while (cnt.size() > 2) {cnt.put(fruits[left], cnt.get(fruits[left]) - 1);if (cnt.get(fruits[left]) == 0) {cnt.remove(fruits[left]);}++left;}ans = Math.max(ans, right - left + 1);}return ans;}
  }
  

總結：

• 第一題讓求大于某個數(shù)的最小子數(shù)組長度

  • while里面最大限度的壓縮，只要滿足就壓縮

  • while的條件是大于某個數(shù)（即滿足題意），并且while每循環(huán)一次就更新一下result的長度

  •         while (sum >= s) {result = Math.min(result, right - left + 1);sum -= nums[left++];}
    

• 第二題讓求最多包含兩類（<=2）的最長子序列長度

  • while里面最小程度的壓縮

  • while里的條件是大于2（即與題意相反），并且是while結束后進行更新長度ans

  •         while (cnt.size() > 2) {cnt.put(fruits[left], cnt.get(fruits[left]) - 1);if (cnt.get(fruits[left]) == 0) {cnt.remove(fruits[left]);}++left;}ans = Math.max(ans, right - left + 1);