<aside> 💡 투 포인터는 웬만해서 정렬을 사용하는 문제를 출제할 경향성이 높음.
</aside>
이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 우선 문제에 주어진 시간은 2초다. 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있는 상태다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 **O(n)**의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 투 포인터다.
연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정해 연속된 수를 표현해보자. 시작과 종료 인덱스를 투 포인터로 지정한 후 문제에 접근
투 포인터 이동 원칙
<aside> 💡 sum > N : sum -= start_index; start_index++; sum < N : end_index++; sum += end_index; sum == N : end_index++; sum += end_index; count++;
</aside>
왜 시간복잡도가 N이냐? 시작과 끝 idx로 모든 수를 훑는데, 위 순서대로 하게 되면 2N의 시간 복잡도가 나오게 되는데, 시간 복잡도에서는 상수는 의미가 없기 때문에 시간 복잡도가 N이 나오게 되는거나
count=1 : 자기 자신 하나로 이뤄진 경우의 수 미리 저장.
