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

4291 단어 cppalgorithmsdsaprogramming
합계가 목표 숫자를 제공할 수 있는 숫자 쌍을 찾아야 하는 상황, 문제를 생각해 보십시오.
예를 들어, 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


    이 기사를 읽어 주셔서 감사합니다.
    좋은 하루 되세요! 🙂
    Next.JS의 기능 플래그
    React에서 배열을 올바르게 렌더링합니다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage