ダブルポインタとスライドウィンドウ

1657 ワード
Algorithm_Theory テキストリンク

1. Two Pointers Algorithm


二重ポインタアルゴリズムとは,N個の一次元配列の中から部分配列の中でMに結合した点を求める.
使用条件では、各要素は自然数であり、Mも自然数でなければ使用できません.アルゴリズムの動作は,まず2つのポインタ(start,end)を指定する.この変数は、各部分配列の先頭と末尾を表します.
Start=0、End=1で、Start<=N-2、End<=N-1に進みます.
次にsum[N]配列を準備し、1次元配列で1...n番目までの和を求める.2つのポインタが移動するルールは簡単です.
  • sum[end]-sum[start]>=Mの場合、startを1つ後ろに移動します.
  • の場合は、末端を1つ後ろに移動します.
    • したがって,startとendを移動し,すべての部分の配列を閲覧すればよい.

    すべての部分配列が本当に遍歴しているかどうかを判断するには、次のような状況が予想されます.
    黒の四角形を現在の部分配列の開始、終了、mとする部分配列をtStart、tEndと呼ぶ.
    その配列を通過するには、StartがtStartを超えなければならないか、EndがtEndを超えなければならないという2つの条件があります.スタート=tスタート時に通過するスタート値は増加する必要がありますが、上記条件M>=を満たす必要があります.ただし、End

    1-1. インプリメンテーション

    SUM[N] = SUM[1...N까지의 합]

start = 0
end = 1

while start < N:
	tempSUM = SUM[end] - SUM[start]
    
    	if tempSUM > M:
        	start += 1
            	해당 조건의 인덱스의 갯수 = end - start + 1
        else:
        	if end != N:
            		end += 1
             	else:
                	start += 1

    2. Sliding Window


    スライドウィンドウがAに簡単に並ぶA[1]...A[N]の部分配列の個数Kが最大部分配列の個数Tよりも大きい場合(K>=T)、共通部分の配列のみを持ち、前面の配列を除く.つまり、スライドウィンドウの任意の配置を右側に移動します.
    for end in range(N):
	tempSum += A[end]
    
    	if end >= ( T - 1 ):
        	resultSum = max(tempSum,resultSum)
            	tempSum -= A[start]
               	start += 1
    JPAのロックとIsolationのテストとレビュー
    深度優先ナビゲーション