투 포인터 알고리즘

배열을 주고 원소의 합이 x 가 되는경우를 찾을떄 

S(N*N) 이므로

 

시간초과가 될 경우가있다 

 

이런경우에 해결하기위해서 

 

투포인터 알고리즘을 사용하면 

S(logN)  또는 정렬시S(N)으로 시간이 대폭 단축될수 있다

 

시작값과 , 마지막값을 저장할 변수 2개 

만약 원소의 합의 갯수를 구한다면 변수 하나

 

sort를 이용해서 정렬을 하고 시작한다 정렬시에는 logN이 N으로 줄어들기 떄문이다

 

예시) 합이 27인 값을 찾아보자

 

int n, s; //13 27  
//1 3 5 6 9 11 12 16 17 19 22 25 28
cin >> n >> s;
 
vector<int>seq(n);
 
for (int i = 0; i < n; ++i)
{
    cin >> seq[i];
}
sort(seq.begin(), seq.end());
 
int l = 0; 
int r = n - 1; 
int ans = 0;
 
while (l<=r)
{
    int sum = seq[l] + seq[r];
    if (sum > s)
    {
        r--;
    }
    else if (sum < s)
    {
        l++; 
    }
    else
    {
        cout << seq[l] <<" " <<l << endl;
        cout << seq[r] <<" " <<r << endl;
        cout << sum << endl;
        cout << endl;
        l++;
        r--;
        
        ans++;
    }
}
cout << ans;