1. Two Sum

문제

Easy

 

Description

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.

 

Examples

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists

 

Solution : One-pass Hash Table

1. 해시 테이블을 만든다.
2. 주어진 배열을 돌면서(iterate)
3. 해시테이블이 <target-현재 element의 값>을 key로 가지고 있는지 확인한다
   
   1. 해당 key가 있다면 그 key의 value는 먼저 방문한 element의 인덱스이므로 해당 인덱스와 현재 element의 인덱스를 반환한다
   2. 해당 key가 없다면 해시테이블에 <key : element의 값, value : element의 인덱스>를 넣는다

 

(english)

1. Create a hash table.
2. Iterate through the given array.
3. Check if the hash table contains the complement of the current element with respect to the target.
   1. If the complement exists as a key in the hash table, return the value of the complement key along with the current element's index.
   2. If the complement does not exist as a key in the hash table, add a new key-value pair where the key is the current element's value and the value is the current element's index.

 

Code (Go)

func twoSum(nums []int, target int) []int {
	hashMap := map[int]int{} // [value]index

	n := len(nums)
	for i := 0; i < n; i++ {
		if prevIndex, ok := hashMap[target-nums[i]]; ok {
			return []int{prevIndex, i}
		}
		hashMap[nums[i]] = i
	}
	return nil
}

 

Complexity Analysis

시간 복잡도 : O(n)

    최악의 경우에도, 주어진 배열을 한번만 순회하게 된다. 해시 테이블에 값이 있는지 확인하는 연산은 O(1)의 시간이 소요된다.

 

공간 복잡도 : O(n)

    hashMap에 배열의 값과 인덱스를 넣게 되어 배열의 크기 만큼의 추가 공간을 사용하게 된다.

 

(english)

Time complexity: O(n)

    We traverse the list containing n elements only once. Each lookup in the table costs only O(1) time.

Space complexity: O(n)

    The extra space required depends on the number of items stored in the hash table, which stores at most n elements.