Two Pointer

- 정렬과 투포인터

input: nums = {4,1,9,7,5,3,16}, target: 14 output: True

nums의 두 숫자를 더해서 target을 만들 수 있으면 True 출력.

 

1. 우선 nums를 오름차순 정렬하기

 nums.sort()

{1,3,4,5,7,9,16}

2. 인덱스 l과 r을 정한다

int l = 0;

int r = nums.length-1;

3. while (l<r) 배열을 돌면서 두 수를 더해보고 값이 다르면 인덱스를 바꾼다.

nums[l] + nums[r] > target ==> r-1. 큰 값을 줄이기

nums[l] + nums[r] < target ==> l+1. 작은 값을 늘리기

4. nums[i]+nums[r] == target ==> return true;

배열을 돌다가 i==r이 되면 return false;

 

시간복잡도: O(nlogn)