Two Pointers

이중 for문의 2차원 선형 탐색으로, (Target값이 발생할 확률이 적은 공간이 포함된) 모든 범위를 훑기 보다

확률이 0인 공간은 배제하되,

중복되는 범위가 없되, 모든 경우의 수를 탐색하도록 한다

 

-

 

Target, sum, marker

 

Target은 인풋으로 주어져 고정되어 있고,

 

sum이 변수인데,

변수를 1부터 증가시키는 방향으로 들어갈 수도 있고

변수를 두 포인터의 (사이의 모든 값들의) 합으로 설정할 수도 있다

(또 Target이 포인터 각기의 합인지, 아니면 사이의 모든 값의 합인지)

 

marking은 당연히 Target == sum일때 marker++; 해주면 됨

 

-

 

pointer의 움직임

 

좌측에서 시작해서 ++ 되는지

양 끝에서 시작해서 s++; or e--; 되는지

 

-

 

시행 필드

 

만약 자연수의 오름차순 배열이면, pointer = value이므로 굳이 배열을 만들지 않고 사용

(규칙 없는) 배열이 필요하다면 배열을 만들어준다

 

 

-

 

작업 공간의 개설(할당)

 

while 회전 공간이이 어디서 시작해서 어디서 종료되는지

- end_pointer가 배열의 끝에 닿으면 종료(e_pointer != A[N])

- 아니면 (s_pointer < e_pointer) 인지

 

-

 

특이 작업

: Arrays.sort(A);

: s++, e--의 움직임에서 두 포인터의 합이 결과로 필요한 경우에는, 두가지 픽이 순열이 아닌 조합으로 들어가므로, 각자 반쪽씩만 탐색하면 된다