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第1 题：两数之和 Go语言精解】本题目是 leetcode 的第一道题目 ， 应该来说是最简单的 ， 况且互联网 ， 特别是 github 上有很多的解题分享 ， 大家很容易知道解题思路 ， 但庖丁还是建议躬身入局 ， 亲自写写代码 ， 提交看看LeetCode 的评价 ， 因为你的测试案例不一定覆盖完全 ， 有思路和实现代码有很大的差距 ， 何况编程本来就是一门重实践的学科 。
参考资料
推荐阅读
- leetcode之错误的集合
- LeetCode 刷题之一（查找常用字符）
- leetcode1614_go_括号的最大嵌套深度
- leetcode哈希表之好数对的数目
- leetcode哈希表之第一个只出现一次的字符
- 程序员面试题：Leetcode真题讲解，求两数之和
- LeetCode|算法｜笔记：第38题：外观数列
- 技术干货（四）「LeetCode」51 - 60题详解
- leetcode之找不同
- 推荐4个基于 Java 语言的 Leetcode 题解项目！算法面试不愁了