Linear 한 리스트에서 두 수의 합 찾기

 

- 문제 상황 :

    주어진 리스트를 O(N)으로 순회하며 그 안에서 target - nums[i]의 꼴로 검색할 경우 O(N^2)의 순회가 되어 시간이 초과된다.

 

- 해결책 :

    먼저 O(NlogN)의 sort 함수를 사용해 nums를 정렬한 후, 인덱스의 시작점과 끝점을 주어 찾는 값이 target보다 작으면 앞쪽 인덱스를 증가시키고 더 크면 뒷쪽 인덱스를 감소시키는 방향으로 찾는다.

 

- Check Point :

    문제에서 주어진 상황이 답이 항상 존재하기 때문에 가능한 방식이다.