1. Two Sum

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example :

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

주어진 정수배열에서 더하여 특정값이 되는 두 숫자의 인덱스를 반환하라.

각 입력에 정확한 하나의 해답이 존재한다고 가정할 수 있으며, 같은 요소를 두 번 사용할 수 없다.

리트코드의 첫번째 문제이다.

첫번째 문제라서 쉬운 편이긴하지만 더해서 target이 되는 숫자값이 아니라 숫자의 인덱스를 반환해야해서 무작정 쉬운 문제는 아니다.

가장 간단하게 푸는 방법은 브루트포스로 for문을 2번 돌리는 것이다.

처음에는 아무 생각 없이 그렇게 풀었는데, 솔루션3번을 보면 원패스 해시 테이블이 있어서 그 내용을 다룬다.

핵심은 요소를 해시테이블에 target과 요소의 차를 키, 인덱스를 값으로 해서 넣어두고,

다른 요소가 그 키가 되면 그 값들이 해답이 되는 것이다.

뭔가 말로 설명하면 복잡하니 하나씩 순서대로 보자.

위의 데이터에서 target만 17로 하겠다. 해답은 2 + 15의 인덱스인 0과 3이 되어야 한다.

１번째 값은 2다. 아직 해시테이블은 비어있는 상태이므로 다음으로 넘어가는데, 다음으로 넘어가기 전에 target과 자신의 차를 해시 테이블에 넣는다.

hashTable : { { 15 : 0 } }이 된다.

2번째 값은 7이다. 해시테이블에 7이 키인 값이 없으므로 다음으로 넘어간다. 마찬가지로 해시테이블에 target과 자신의 차를 넣는다.

hashTable : { {15:0}, {10:1} }

3번째 값은 11이다. 해시에 11의 키가 없으므로 다음.

hashTable: { {15:0}, {10:1}, {6:2} }

4번째 값은 15이다. 해시 테이블에 15가 키인 값이 있다. 15가 키인 인덱스는 0이고 나 자신은 인덱스가 3이므로, 해답은 [0, 3]이 되겠다.

문제의 조건에는 없는데 만약에 배열이 정렬된 값이라면 요소의 값이 target을 넘어가는 순간 멈춰도 될 듯 하다.