[프로그래머스, 연속된 부분 수열의 합] JAVA로 풀이

처음에 완전탐색하면서 for문 2개를 이용해서 풀었는데, 시간제한이 걸렸다. 도저히 방법이 생각이 안 나서, 풀이 과정을 찾아서 투포인터 알고리즘이라는 걸 알게 됐다.

투포인터 알고리즘 1) left, right 라는 포인터를 설정, 배열의 첫번째 인덱스를 가리키게 된다. 2) 또, sum을 설정해 left에서 right까지의 합을 갖게 된다. sum을 다시 설장한다. 3-1) sum이 구하려는 수보다 작으면 right를 증가시킨다. sum을 다시 설장한다. 3-2)크면 left를 증가시킨다. 3-3)같으면 찾았다. 하지만, 같은 경우가 더 있을 수 있으니 계속 탐색한다.

이때, left와 right값을 증가시켜주고 sum을 다시 설장한다. 이렇게 하면서 left와 right가 인덱스 범위를 안 넘게 탐색한다.

시간 복잡도 left가 첫번째 인덱스를 가리키고, right가 하나씩 증가하면서 끝까지 간 다음, 거기서 멈춘다. 또, 이번엔 left가 하나씩 증가하면서 left가 끝까지 ...