スライディングウィンドウ（尺取り法）

配列の連続する部分列を効率的に処理する重要な技法を学ぼう

O(n)

時間計算量

O(1)

空間計算量

中級

難易度

その他

カテゴリ

🔧 実行設定

操作:

fixedSize

配列:

[1, 3, 2, 6, -1, 4, 1, 8, 2]

配列（カンマ区切り）

ウィンドウサイズ

目標和

文字列（部分文字列用）

💡 推奨操作

🪟

アルゴリズムを実行してください

左側の設定パネルから操作を選択し、「アルゴリズム実行」ボタンを押してください

💻 実装例（JavaScript）

// 固定サイズウィンドウの合計
function fixedWindowSum(arr, windowSize) {
    const result = [];
    let windowSum = 0;
    
    // 最初のウィンドウ
    for (let i = 0; i < windowSize; i++) {
        windowSum += arr[i];
    }
    result.push(windowSum);
    
    // ウィンドウをスライド
    for (let i = windowSize; i < arr.length; i++) {
        windowSum = windowSum - arr[i - windowSize] + arr[i];
        result.push(windowSum);
    }
    
    return result;
}

// 尺取り法（可変サイズウィンドウ）
function twoPointers(arr, targetSum) {
    let left = 0, right = 0;
    let currentSum = 0;
    
    while (right < arr.length) {
        currentSum += arr[right];
        
        while (currentSum > targetSum && left <= right) {
            currentSum -= arr[left];
            left++;
        }
        
        if (currentSum === targetSum) {
            return { found: true, left, right };
        }
        
        right++;
    }
    
    return { found: false };
}

// 最長非重複部分文字列
function longestUniqueSubstring(s) {
    const charSet = new Set();
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        
        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

// 使用例
const arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];
console.log(fixedWindowSum(arr, 3)); // [6, 11, 7, 9, 4, 13, 11]
console.log(twoPointers([1, 4, 2, 3, 5], 7)); // {found: true, left: 1, right: 2}
console.log(longestUniqueSubstring("abcabcbb")); // 3

🔧 実行設定

💡 推奨操作

アルゴリズムを実行してください

スライディングウィンドウ（尺取り法）とは？

💻 実装例（JavaScript）