수들의 합2
BOJ 2003 수들의 합 2 [Java]
BOJ 2003 수들의 합2 - 문제 링크 https://www.acmicpc.net/problem/2003 - 문제 해설 전형적인 투포인터 알고리즘을 이용할 수 있는 문제이다. 2중 for문을 이용하면 시간 복잡도가 O(N^2)으로 제한 시간을 맞출 수 없지만, 투 포인터를 이용하면 O(N)으로 시간이 충분하다. 시작점을 가리키는 포인터를 start, 끝 점을 가리키는 포인터를 end, 포인터가 가리키는 두 원소의 합을 sum, 찾고자 하는 경우의 갯수를 cnt라고 하자. 1) 두 원소의 합이 M이면 구하고자 하는 경우를 찾았으니 cnt를 1 더해준다. start가 가리키는 원소의 값을 sum에서 빼주고 start를 1 더해준다. end를 1 더해주고 더해진 end가 가리키는 원소의 값을 sum에 더해..