[LeetCode] 0001. Two Sum

문제

주어진 정수 배열에서 서로 다른 두 수의 합이 목표 값이 될 때, 두 수의 인덱스를 배열 형태로 반환해라.

입력하는 값은 하나의 답만 존재하며, 같은 수를 두 번 사용할 수 없다. 즉, 같은 인덱스를 두 번 반환해서는 안된다.

 

풀이

1.Brute Force (무차별 대입)

처음부터 하나씩 수를 대입해서 목표 값이 같아질 때까지 반복하여 찾은 인덱스 값을 반환한다.

Time Conplexity(시간 복잡도): O(N²) - 2중 반복문 사용

Space Conplexity(공간 복잡도) : O(1): 따로 값을 저장하지 않고 입력받은 값만 사용

2. Two pass hast table (해시 테이블 2번 통과)

해시 테이블의 key가 배열의 값이고, 해시 테이블의 value가 배열의 인덱스인 해시 테이블은 먼저 만든다.

목표 값에서 정수 값을 뺀 나머지 값이 해시 테이블에 있다면 현재 인덱스와 해쉬 값을 반환한다.

Time Conplexity(시간 복잡도): O(N) - 반복문이 단독으로만 사용

Space Conplexity(공간 복잡도) : O(1): N개의 값이 든 해시 테이블 만들어서 사용

3. One pass hash table (해시 테이블 1번 통과)

2번 풀이에서 공간 복잡도를 줄인 방법으로 해시 테이블을 만들면서 값을 찾는 방법이다.

먼저 목표 값에서 해당 배열 값을 뺀 나머지 값이 해시 테이블에 존재하는지 확인한다.

값이 존재 하지 않으면, 배열의 값이 Key고, 배열의 인덱스가 value인 데이터를 해쉬 테이블에 추가하고, 있다면 해쉬의 값과 현재 인덱스를 반환한다.

Time Conplexity(시간 복잡도): O(N) - 반복문이 단독으로만 사용.

Space Conplexity(공간 복잡도) : O(N): 최대 N개의 값이 든 해시 테이블이 만들어짐.

 

해당 문제를 풀고자하시면 이 링크를 누르면 문제를 풀 수 있고, 문제 풀이 코드는 이 링크를 클릭하면 됩니다.