2 つのポインターとスライディング ウィンドウ - AI がデータを効率的にスキャンする方法

スマートなスキャンが重要な理由

AI がライブ ビデオ フィードで不審なアクティビティを監視していると想像してください。録画全体を毎秒再視聴することはできません。ストリーム全体に注意を向けるウィンドウをスライドさせて、十分なコンテキストを追跡する必要があります。これはまさに 2 つのポインター と スライディング ウィンドウ パターンが順次データに対して行うことです。

どちらの手法も、総当たりの O(n²) スキャンをエレガントな O(n) パスに変換します。

ツーポインターテクニック

2 つの参照をシーケンスに配置し、ルールに従って移動します。味は大きく分けて2つあります。

収束するポインター

それぞれの端から 1 つのポインターを開始し、それらを内側に移動します。 並べ替えられたデータに最適です。

古典的な問題 - ペアの合計: ソートされた配列を指定して、ターゲットに加算する 2 つの数値を見つけます。

function pairSum(arr, target):
    left = 0
    right = arr.length - 1
    while left < right:
        sum = arr[left] + arr[right]
        if sum == target: return (left, right)
        if sum < target: left += 1
        else: right -= 1
    return null

配列はソートされているため、leftを右に移動すると合計が増加し、rightを左に移動すると合計が減少します。これにより、有効なペアを見逃さないことが保証されます。

同じ方向のポインタ

どちらのポインタも前に進みますが、速度が異なります。 パーティション化またはサイクル検出に役立ちます。

例 - 重複をその場で削除します。 遅いポインタは書き込み位置をマークします。高速ポインターは前方をスキャンします。

function removeDuplicates(arr):
    slow = 0
    for fast in 1..arr.length - 1:
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1

スライディング ウィンドウ パターン

スライディング ウィンドウは、サイズ k (固定) または可変長の連続したサブシーケンスを維持し、最初から再計算するのではなく、集計を段階的に更新します。

固定サイズのウィンドウ

正確に k 個の要素のウィンドウを配列全体にスライドさせます。

例 - k 個の連続する要素の最大合計:

function maxSubarraySum(arr, k):
    windowSum = sum(arr[0..k-1])
    best = windowSum
    for i in k..arr.length - 1:
        windowSum += arr[i] - arr[i - k]
        best = max(best, windowSum)
    return best