🤸

2023/06/03に公開

# Two Sum

## 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.

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 <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

## Approach

Naive Solution : Brute force.
Optimal Solution : HashTable.

## Solution

liner scan array left -> right, and build map

// index=0
`map=[], target=9, nums[index]=2;`
If exist key `2`, return current index `0` and the value stored under the key `2`.
else store `7(9-2)` as key, current index `0` as value.

// index=2
`map[(7,0),(2,1)], taget=9, num[index] = 11`
If exist key `11`, return current index `2` and the value stored under the key `11`.
else store `-2(9-11)` as key, current index `2` as value.

// index=3
`map[(7,0),(2,1),(-2,2)], taget=9, num[index] = 15`
If exist key `15`, return current index `3` and the value stored under the key `15`.
else store `-4(9-15)` as key, current index `3` as value.

So code below
If exist key `num[index]`, return current `index` and the value stored under the key `num[index]`.
else store `x(target-num[index])` as key, current `index` as value.

## Code

``````func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for index, num := range nums{
val, has := m[num]
if(has){
return []int{val,index}
}
m[target-num] = index
}
return []int
}
``````

## Big-O Runtime & Space Complexity

• Runtime Complexity O(n) : single pass liner scan of nums[]
• Runtime Complexity O(n) : need to store all the items in hashmap in the worst case, so O(n) space

## Go Grammar

### Short Variable Declarations

Inside a function, the `:=` short assignment statement can be used in place of a var declaration with implicit type.

Outside a function, every statement begins with a keyword (`var`, `func`, and so on) and so the `:=` construct is not available.

### Initializeing Map in Go

1 : Built in make function

To initialize a map, use the built in make function:
`map = make(map[string]int)`

2 : With data

To initialize a map with some data, use a map literal:
`commits := map[string]int{ "rsc": 3711, "r": 2138, "gri": 1908, "adg": 912, }`

### Check Existence of A Key in Map

`i, ok := m["route"]`
In this statement, the first value (i) is assigned the value stored under the key "route". If that key doesn’t exist, i is the value type’s zero value (0). The second value (ok) is a bool that is true if the key exists in the map, and false if not.
p
To test for a key without retrieving the value, use an underscore in place of the first value:
`_, ok := m["route"]`