しゃくとり法やSliding Windowの個人的な実装テンプレート

しゃくとり法やSliding Windowと呼ばれるアルゴリズムの実装テンプレートです。これを利用する問題にぶつかるたび、どう実装するか忘れてしまうので、自分用に残しておきます。実装方法にはいろいろ流儀があるようですが、個人的には以下の形式が好みです。

let mut right = 0;
for left in 0..n {
    while right < n && 【条件を満たすか? (ex. sum+a[right]<k)】{
        【rightを1進める (ex. sum+=a[right])】
        right += 1;
    }

    【この時点で[left, right)は条件を満たす最大になっているので、処理を行う】
    【ex. ret+=right-left】

    if left == right {
        right += 1;
    } else {
        【leftを1進めるための前処理 (ex. sum-=a[left])】
    }
}

利用例: LeetCode 713. Subarray Product Less Than K

積がk未満の部分配列の数を求める問題です。

impl Solution {
    pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut right = 0;
        let mut product = 1;
        let mut ret = 0;

        for left in 0..n {
            while right < n && product * nums[right] < k {
                product *= nums[right];
                right += 1;
            }

            ret += right - left;

            if left == right {
                right += 1;
            } else {
                product /= nums[left];
            }
        }
        return ret as i32;
    }
}