内容简介:在文章正式开始之前, 首先有几点需要特别说明: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.
在文章正式开始之前, 首先有几点需要特别说明:
- 本文所有代码都托管在 Windary: https://github.com/TonnyL/Windary , 如果你发现了错误, 请通过 issue 或其他方式指出, 但是暂时 不 接受 Pull Request;
- 我提供的算法仅供参考, 并不代表最佳的解法(有的解法可能爆机, 有的解法可能刚好踩线 AC);
-
文章使用
Go
作为主要描述语言, 同时也会在每一道题的末尾附加其他语言描述的解法的地址及其 AC 情况(选用 Go 是因为她的代码量最少); -
所有的解法都有相应单元测试用例:
-
Go: 测试用例文件与解法同级位于同级目录下, 例如解法文件
TwoSum.go
的路径为Windary/Golang/TwoSum/TwoSum.go
, 则测试用例文件TwoSum_test.go
的路径为Windary/Golang/TwoSum/TwoSum_test.go
, 所有的测试用例文件均以 解法文件名 + _test 的形式命名; -
Java: 测试用例与解法文件均位于
src
目录下, 例如解法文件TwoSum.java
的路径为Windary/Java/src/TwoSum.java
, 则测试用例文件TwoSumTest.java
的路径为Windary/Java/src/TwoSumTest.java
, 所有的测试文件均以 解法文件名 + Test 的形式命名; - JavaScript: 测试用例与解法文件为同一个文件, 解法文件在前, 测试用例在后;
- Kotlin: 与 Java 代码组织形式一致;
-
Python: 测试用例文件与解法文件均位于
Python
目录下, 例如解法文件TwoSum.py
的路径为Windary/Python/TwoSumTest.py
, 则测试用例文件的路径为Windary/Python/TwoSumTest.py
, 所有的测试文件均以 解法文件名 + Test 的形式命名; -
Swift: 所有的解法文件位于
Windary/Swift/LeetCode/LeetCode/
目录下, 所有的测试用例文件位于Windary/Swift/LeetCode/LeetCodeTests/
目录下, 测试用例文件以 解法文件名 + Tests 的形式命名.
-
Go: 测试用例文件与解法同级位于同级目录下, 例如解法文件
1. 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].
1. 两数之和
给定一个整数数列,找出其中和为特定值的那两个数。
你可以假设每个输入都只会有一种答案,同样的元素不能被重用。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
思路:
循环遍历, 这种方法时最容易想到的. 时间复杂度为 O(n2).
解法(Go):
func twoSum(nums []int, target int) []int { numsLength := len(nums) for i := 0; i < numsLength; i++ { for j := i + 1; j < numsLength; j++ { if target == (nums[i] + nums[j]) { return []int{i, j} } } } return []int{0, 0} }
其他解法:
上面的解法还可以改进, 可以先使用快速排序(时间复杂度 O(nlogn)), 然后双指针从前后往中间扫描. 但是题目要求是返回数组下标, 所以还需要额外的空间存放下标信息.
另外一种方法则是通过 Hash 的方式. 从前往后扫描一遍, 将数及下标存放到 Map 中, 再次扫描即可. 时间复杂度为 O(n).
AC 情况:
# | Title | Go | Java | JavaScript | Kotlin | Python | Swift | Difficulty |
---|---|---|---|---|---|---|---|---|
1 | Two Sum | √ | √ | √ | √ | √ | √ | Easy |
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 欣赏一个简洁利落的解法
- 欣赏一个简洁利落的解法
- Script error 问题解法
- 一道SQL题的多种解法
- Leetcode 139. WordBreak 解法和思路
- 【日拱一卒】链表——链表反转(递归解法)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
PHP&MySQL Web数据库应用开发指南
Hugb E. Williams、David Lane / 谢君英 / 中国电力出版社 / 2003-5 / 69.00元
一起来看看 《PHP&MySQL Web数据库应用开发指南》 这本书的介绍吧!