Problem:
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.
Example:
|
1 2 3 4 |
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. |
The returned answers should be zero-based.
Solutions:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
func twoSum(nums []int, target int) []int { result := make([]int, 2) var i, j int n := len(nums) for i = 0; i < n-1; i++ { for j = i + 1; j < n; j++ { if nums[i]+nums[j] == target { result[0] = i result[1] = j return result } } } return result } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
func twoSum(nums []int, target int) []int { var temp int var flag bool record := make(map[int]int) result := make([]int, 2) for i, v := range nums { temp, flag = record[target-v] //Retrieve `record[target-v]` first to avoid duplicate record[v] = i if flag == true { result[0] = temp result[1] = i return result } } return result } |
Brute Force 不值一提，本该用 HashTable 解决的问题在遇到了 Go 自带的 map 后就变得十分简单了，虽然写一个开地址哈希表也并不费事。