アルゴリズム:ダブルポインタ

6012 ワード
アルゴリズム#アルゴリズム# テキストリンク

ダブルポインタアルゴリズム


1 Dアレイ内の2つの異なる要素を持つポインタを移動して、正しい答えを得ます.

モード


2つのポインタ(start,end)をそれぞれ0に設定して移動する.
ex) 
10 5
1 2 3 4 2 5 3 1 1 2 에서 5인 합 갯수 세기
left: 빨간색 ,right: を青とし、rightを徐々に再生する.

この地点では合計5を超えるため、left増加した.

同様に、合が5の場合にカウントダウンを行い、leftを増やす.

この地点では合計5を超えるため、left増加した.

同様に、合が5の場合にカウントダウンを行い、leftを増やす.

このように増加すると、rightは終了します.これ以上はできないからです.

コード#コード#

#include <cstdio>
    using namespace std;

int main()
{
    int n = 10; //n: 배열
    int m = 5;  //m : 합
    int cnt = 0;
    int s = 0;
    int arr[] = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2};
    int left = 0, right = 0;
    while (1)
    {
        if (s >= m)
            s -= arr[left++];
        else if (right == n)
            break;
        else
            s += arr[right++];
        if (s == m)
            cnt++;
    }
    cout << cnt << '\n';
}

時間の複雑さ


ポインタの増加はnごとにしか増加しないので,配列の末尾に達すると終了する.
すなわち、時間的複雑度はO(n)である.

スライドウィンドウ


配列またはリスト内の要素の一定範囲の値を比較する場合に有用なアルゴリズムです.
ダブルポインタとの違いは、どの瞬間でもその区間の幅が同じであることです.
ex) 
10 5
1 2 3 4 2 5 3 1 1 2 에서 구간의 넓이가  [2]일 때, 최대 합을 구하여라

時間の複雑さ


同様に,時間複雑度はO(n)であった.

ソース
https://m.blog.naver.com/kks227/220795165570
https://www.youtube.com/watch?v=uH9VJRIpIDY
ArrayListと反復器およびストリーム
【白俊】1912号:連合