「右端を固定して、左端を動かす」タイプのしゃくとり法・Sliding Windowの実装テンプレート

以前、しゃくとり法・Sliding Windowの実装テンプレートに関する記事を書いたことがあります。

この記事では「左端を固定して、右端を動かす」タイプについて書いたのですが、問題によっては「右端を固定して、左端を動かす」ほうが適切なことがあります。そこで、本記事では、後者の「右端を固定して、左端を動かす」テンプレートを紹介したいと思います。

int left = 0;
for (int right = 0; right < n; right++) {
  【rightを1進める (ex. sum+=a[right])】

  while (【条件を満たすか? (ex. sum<k)】) {
    【この時点で[left, right]は条件を満たす最大になっているので、処理を行う】
    【ex. ret+=n-right】
    
    【leftを1進めるための前処理 (ex. sum-=a[left])】
    left += 1;
  }
}

leftとrightは閉区間になっていることに注意しましょう。また、問題によっては、while句の条件判定の際、left <= rightのチェックを行う必要がある場合があります。

利用例 : LeetCode 2537. Count the Number of Good Subarrays

import java.util.HashMap;
import java.util.Map;

public class Solution {
  public long countGood(int[] nums, int k) {
    Map<Integer, Integer> d = new HashMap<>();
    int pair = 0;
    long ret = 0;

    int n = nums.length;
    int left = 0;
    for (int right = 0; right < n; right++) {
      pair += d.getOrDefault(nums[right], 0);
      d.put(nums[right], d.getOrDefault(nums[right], 0) + 1);

      while (pair >= k) {
        ret += n - right;
        d.put(nums[left], d.get(nums[left]) - 1);
        pair -= d.get(nums[left]);
        left += 1;
      }
    }

    return ret;
  }
}