두 개의 숫자를 찾는 두 포인터 방법

합계가 목표 숫자를 제공할 수 있는 숫자 쌍을 찾아야 하는 상황, 문제를 생각해 보십시오.
예를 들어, x+y = 타겟
여기에서 배열, 목록, 벡터 또는 배열이 정렬된 다른 순차적 데이터 구조에서 x,y를 찾아야 합니다.

무차별 접근

한 요소를 가져와 다른 요소와 함께 추가합니다.

이러한 요소의 합이 목표와 같아질 때까지 이 작업을 수행합니다.
따라서 최악의 경우

시간 복잡도 - O(n^2)

두 포인터 방법

start 및 end 두 변수를 사용합니다.

배열의 첫 번째 요소를 가리키는 start.

end가 배열의 마지막 요소를 향하도록 가리킵니다.

이제 원하는 결과를 얻을 때까지 while 루프를 실행해 보겠습니다.
조건 - start + end == target .

start + end > target이면 왼쪽으로 end 이동합니다.

start + end < target이면 start 오른쪽으로 이동합니다.

따라서 이 기술을 사용하여 이 문제를 다음과 같이 해결할 수 있습니다.
시간 복잡도 - O(n)

// Program to get two numbers from array whose sum is equal to target element.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[10] = {1, 4, 6, 8, 9, 12, 14, 16, 17};
    int target = 20, start = 0, end = 8;
    while ((a[start] + a[end] != target) && (start < end))
    {
        if (a[start] + a[end] > target)
        {
            end--;
        }
        else
        {
            start++;
        }
    }
    cout << "Two numbers are: " << a[start] << ", " << a[end] << endl;
    return 0;
}

// Code contributed by Kunal Agrawal

이 기사를 읽어 주셔서 감사합니다.
좋은 하루 되세요! 🙂