Golang LeetCode - 1. Two Sum 两数之和

Avery_up · · 1432 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一次，站长亲自招 Gopher 了>>>

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

思路分析

参数：一个数字数组nums，一个目标数target。
目标：让找到两个数字(同一个数字不能使用两次)，使其和为target。
分析：暴力搜索的话是遍历所有的两个数字的组合计算其和，这样节省了空间，但是时间复杂度高。为了减少时间的复杂度，需要用空间来换。
只遍历一次数组，在遍历的同时将数据使用HashMap存储起来，翻转key和value，建立数字和其坐标位置之间的映射。HashMap 是常数级的查找效率，这样在遍历数组的时候，用 target 减去遍历到的数字，就是另一个需要的数字了。直接在 HashMap 中查找其是否存在即可。
由于当前数字在HashMap中还不存在，所以不会出现同一个数字使用两次的情况。比如 target 是4，遍历到了一个2，另外一个2还未进入HashMap中，肯定就是要找的值。
整个实现步骤为：遍历一遍数组，查找target 减去当前数字是否存在于HashMap中；如果不存在，则建立 HashMap 映射。代码如下：

Go代码

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for k, v := range nums {
        idx, ok := m[target - v]
        if ok {
            return []int{idx, k}
        }
        m[v] = k
    }
    return nil
}
// nums := []int{2, 7, 11, 15}
// target := 9
// result [1 0]

有疑问加站长微信联系（非本文作者）