题目【LeetCode第1 题：两数之和 Go语言精解】本题目来自 LeetCode 的第一道题 ， 题目地址：
题目描述原题目英文描述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.
题目中文翻译给定一个整数数组 nums 和一个目标值 target ， 在该数组中找出和为目标值的两个整数 ， 并返回它们的数组下标 。
可以假设每种输入只会对应一个答案 。 但是 ， 数组中同一个元素不能使用两遍 。
Example 1:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].示例 2
Input: nums = [3,2,4], target = 6 Output: [1,2]示例3
Input: nums = [3,3], target =Output: [0,1]解题思路
文章插图
聚焦核心问题
使用暴力破解法 使用两层循环来寻找满足之后的两个数字 ， 示例Go 语言代码如下 ：
func twoSum(nums []int, target int) []int { for i, num := range nums {for j, value := range nums {if i!=j--tt-darkmode-color: #707070;">Runtime: 56 ms, faster than 9.32% of Go online submissions for Two Sum.
Memory Usage: 2.9 MB, less than 61.24% of Go online submissions for Two Sum.
可以看出时间复杂度很一般 ， 可以说非常糟糕。 这里的主要效率低的原因是寻找数组中的另一个数字遍历了整个数组 ， 造成效率低下 ， 我们知道时间复杂度为的数据结构有 Map ， 我们可以使用 Map 数据结构 ， 将整个算法的复杂度降低到?,下面看看改进后的Go 语言代码 ，
func twoSum(nums []int, target int) []int { m := make(map[int]int, len(nums)) for idx, num := range nums {if i, ok := m[target-num]; ok {return []int{i, idx}} else {m[num] = idx} } return nil}我们再来看看 LeetCode 的评价结果， 可以看出效果不错
Runtime: 4 ms, faster than 94.09% of Go online submissions for Two Sum.
Memory Usage: 3.4 MB, less than 61.24% of Go online submissions for Two Sum.
使用一个 Hash 表来存储结果 ， 算法的时间复杂度为O(n) ， 空间复杂度为O(n)
庖丁点评本题目是 leetcode 的第一道题目 ， 应该来说是最简单的 ， 况且互联网 ， 特别是 github 上有很多的解题分享 ， 大家很容易知道解题思路 ， 但庖丁还是建议躬身入局 ， 亲自写写代码 ， 提交看看LeetCode 的评价 ， 因为你的测试案例不一定覆盖完全 ， 有思路和实现代码有很大的差距 ， 何况编程本来就是一门重实践的学科 。
参考资料