오름차순으로 정렬되어 있는 배열의 구간합이 k가 될 때, 해당하는 시작 인덱스, 끝 인덱스를 반환 하는데 여러개 라면 길이가 짧은 것을, 길이도 같다면 시작인덱스가 작은 것을 반환하는 문제였다.
먼저 내 생각으로 구간합을 구하기 위해서 한개의 배열에 대하여
index i, j
[0, 1, 2, 3, 4]
i = 0 j = 1 -> 0(i) 부터 1(j) 까지의 구간합
i = 0 j = 2 -> 0(i) 부터 2(j) 까지의 구간합
i = 0 j = 3 -> 0(i) 부터 3(j) 까지의 구간합
이런식으로 완전탐색하여 k와 값이 같은 값을 정답 배열에 넣어 준 후 정렬하기 위하여 시도하였고, 구현했다. 하지만 시간초과.
해당 문제를 2중 for문으로 이루어진 O(n^2)의 시간복잡도를 가진 풀이가 아닌 O(n) 시간복잡도를 풀이를 사용해야 했다. 그러기 위하여 등장한 것이
투포인터
한번의 반복 횟수 마다 2개의 포인터(start, end)를 운용하는 방법이다.
먼저 start와 end 인덱스를 지정하고 (포인터 2개)
start보다 end가 같거나 작을 때만 동작한다.
일련의 동작을 설명하면 이렇다.
1. start 부터 end 까지의 부분합이 원하는 값보다 작으면 end를 한칸 올려 부분합의 범위를 늘려준다
2. start 부터 end 까지의 부분합이 원하는 값보다 크면 start를 한칸 올려 부분합의 범위를 줄여준다.
3. 부분합이 원하는 값과 같다면 해당 요소를 저장하고 계속 탐색할 수 있도록 end를 한칸 올려 범위를 늘려준다.
