Two Sum - LeetCode

문제 파악

1. 배열 내부에 있는 요소들의 합이 우리가 원하는 target 정보와 일치하는 경우에 해당 인덱스 두 가지를 리턴
2. 제공되는 nums 는 중복되는 숫자가 있을 수 있고, 두 개를 결정한다는 특징이 존재
3. 정답이 될 수 있는 답은 하나

[제약 사항]

10^4 까지 이뤄지기 때문에 O(n^2) 의 경우에는 10^8 까지 이뤄질 수 있어, 위험할 가능성이 있다.

접근 방법

1. O(n^2)의 해결 방법 (완전 탐색)

중첩 반복문을 활용하여 배열의 각 요소를 돌며, sum이 target과 같은지 확인

1. nlogn의 해결 방법?

좀 더 개선하는 방법? (nlogn, logn 정도 있을 것 같다.)

nlogn은 정렬의 시간 복잡도 → 리스트를 정렬하면 새로운 방식이 보이지 않을까?

좌, 우에서 차례대로 접근하면서 쓸 수도 있지 않을까?