투포인터
-
1차원 배열이 있고, 이 배열에서각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태 -
N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것 -
모든 경우의 수를 다 테스트 해보면 구간 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이 되기 때문에 문제를 풀 수 없음
시간 복잡도
- 이 알고리즘은 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝남
- 따라서 각각 배열 끝에 다다르는데 O(N)이라서 합쳐도
O(N)이 됨
