Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
다시 말해, 이 문제에서 해결하고자 하는 문제는
주어진 배열에 대한 각 정수에 대하여 두개의 각기 다른 인덱스의 정수의 합이 target과 같도록 두개의 인덱스를 반환해라.
몇가지 방법이 있는데 내가 처음 생각난 방법은 Brute Force이다. 말 그대로 하나하나씩 일일히 짝을 찾아보는것이다. 예를들어, [2,7,11,15]의 배열이 있고, 타겟이 9일때, for문을 돌면서 비교한다. 예를들어, 배열의 첫번째 요소인 2부터 시작해서 이중 for문을 사용하여 그 다음 요소와 계속 비교한다. 그렇지만 이 문제에서는 정확한 두개의 인덱스를 반환해야하고, 배열은 정렬되어 있지 않기 때문에 수많은 탐색 시간이 소요된다. - O(n^2).
두번째 - 두개의 포인터를 이용.[해시테이블]
먼저 해시 테이블에 대해 알아야 한다. 해시 테이블이란 Key-Value pair로 매핑되는 가장 중요한 자료구조중 하나로써, 해시 함수를 이용한 삽입, 검색, 삭제에서 낮은 시간복잡도를 보인다[해시 테이블에 대해 잘 모른다면 유튜브나 구글링을 해보면 쉽게 이해 할 수 있다]. 그렇다면 위의 문제에서 해시 테이블을 어떻게 활용해야할까? [파이썬 에서는 해시맵이나 테이블 대신 딕셔너리 라고 부른다.] {} 기호로 표시한다.
먼저 리턴값을 생각해보자. 우리는 두개의 인덱스를 리스트형태로 반환해야 한다. 두개의 값을 더해 의도된 정수값이 나오는 방법을 생각해보자.
1. 리스트를 순회하며 타겟값에서 리스트의 정수값을 뺀다.
- 이유는 예를들어 타겟이 9이고 리스트의 0번째 정수가 2라면 9에서 2를 뺀 7을 리스트에서 찾아내면 그대로 반환하면 된다.
이해가 안 간다면 다시, 주어진 리스트 list = [1,5,3,12,9], 타겟을 10이라고 해보자. 이 리스트에서 가능한 조합은 1+9 이다. 리스트의 순서는 상관 없다고 했으므로 리턴되는 리스트 값은 [0, 4] 또는 [4,0]이여야 한다.
자 그렇다면 위의 내용을 코드로 어떻게 구현할까?
파이썬의 딕셔너리(aka HashTable)은 {} 이 기호로 표시해준다. 자료구조 수업에서는 자바를 이용했는데 해시맵을 import하고 객체를 만들때도 HashMap<Integer> map = new HashMap<>(); 처럼 직접 자료형을 선언해줬어야 했는데 이런거 보면 파이썬은 다른 프로그래밍 언어보다 훨씬 간결해보인다.
1. 딕셔너리 선언하기
numDictionary = {}
{}로 표현한 딕셔너리에 numDictionary라는 이름을 부여해줬다. 이제 우리의 딕셔너리는 이 이름으로 참조하면 된다.
2. 반복문
이제 반복문을 통해 리스트를 순회하면서 주어진 값을 찾아야 한다. 가독성이 쉽도록 리스트의 길이는 변수로 만들겠다.
반복문중에서 가장 많이 쓰이는 for문은 파이썬에서 이렇게 쓰인다.
n = len(list)
for i in range n :
complement = target - nums[i]
여기서의 complement는 타겟값에서 리스트의 정수를 뺀것이다. 즉, 이 변수는 우리가 리스트에서 찾아야 할 값이다.
3. 조건문
파이썬의 여러가지 메서드중 편리한 built-in 메서드가 있는데, if a in b 메서드이다.
b안에 a가 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. 여기서의 a는 딕셔너리 안의 "키값"을 참조한다. b의 자료형은 리스트, 딕셔너리, 튜플, 문자열(즉, 순서가 있는) 모두 가능하다.
이제 조건문을 통해 우리가 계산한 complement(보수, 즉 찾아야 할 값)이 리스트 안에 있는지 확인해보면 된다.
n = len(list)
for i in range n :
complement = target - nums[i]
if complement in numDictionary :
return [numMap[complement], i]
numDictionary[nums[i]] = i #key - value 매핑
return []
if문을 살펴보자. 만약 딕셔너리 안에 보수가 있다면 현재 루프의 기준 인덱스 i와 그 보수값의 인덱스를 찾아 리턴하면 된다. 만약 딕셔너리 안에 찾으려는 보수값이 없다면, 딕셔너리 안에 키-값으로 매핑된 값을 넣어준다. 여기서의 Key는 리스트에서의 인덱스 i에 해당하는 값이고, value는 for문을 도는 기준값 i이다. 원하는 값이 없다면 비어있는 리스트를 리턴한다.
위에서 든 예시를 다시 코드와 함께 보자.
주어진 리스트 [2,7,11,15], 타겟은 9이고, 텅 빈 딕셔너리{} 가 있다. 리스트의 길이는 4이고, for문을 돈다면 0부터 3까지 순회할것이다.
- 첫번째 루프 (i = 0)
- complement = 9 - nums[0] = 7 이다.
- if 7 in numDictionary : => 현재 딕셔너리는 비어있으므로 False를 반환하고 if문 밖으로 빠져 나간다.
- numDictionary[nums[0]] = 0 => 딕셔너리 안에 키 2, value값 0을 매핑해준다. {2 : 0}
- 두번째 루프 (i = 1)
- complement = 9 - nums[1] = 2 이다.
- if 2 in numDictionary : 현재 딕셔너리에 2 라는 키값이 존재하는지 확인한다. 근데 우리가 위에서 {2 : 0}의 쌍을 딕셔너리에 추가했다. 그렇다면 이 조건문은 true가 반환되어 if문 안의 리턴문이 실행될것이다.
- 리턴 타입은 리스트로 지정되었기 때문에, return []형식으로 리스트를 반환한다. 첫번째 반환값은 numDictionary[2]이다. 이렇게 하면 딕셔너리에서 키값 2에 해당하는 value를 찾아 리턴할 것이다. 위에서 우리는 딕셔너리에 {2 : 0}을 매핑하였으므로 위의 구문에선 0이 리턴된다.
- 그 다음 리턴값은 현재 순회중인 i값을 나타낸다. 그렇다면 차례로 [0, 1]이 리턴되고, 주어진 리스트 nums = [2,7,11,15]에서 0번째, 1번째 값 (2 + 7)은 9이므로 정답이다.
