-
-
Notifications
You must be signed in to change notification settings - Fork 737
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[LeetCode] 1. Two Sum #1
Comments
解法二 输出为逆序 有误 |
Java的解法二输出结果错了 |
Solution in ReasonML/OCaml.
|
|
|
rust解法 fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut m = HashMap::new();
for (i, j) in nums.iter().enumerate() {
if m.contains_key(&(target - j)) {
let mut res = vec![i as i32, *m.get(&(target - j)).unwrap()];
res.reverse();
return res;
}
m.insert(j, i as i32);
}
vec![]
} |
go解法
|
JS 解法
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
请点击下方图片观看讲解视频
Click below image to watch YouTube Video
Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up totarget
.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.
Example 1:
Example 2:
Example 3:
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Follow-up: Can you come up with an algorithm that is less than
O(n2)
time complexity?啦啦啦,欢迎开启 LeetCode 刷题的旅程,这将是一段漫长而又艰辛的旅程,这是一条攀登珠穆朗玛的皑皑雪山路,这是通向 One Piece 宝藏的伟大航路,这是成为火影的无比残酷的修罗场,这是打破吊丝与高富帅之间界限的崩玉。但请不要害怕,在老船长 Grandyang 博主的带领下,必将一路披荆斩棘,将各位带到成功的彼岸,不过一定要牢记的是,不要下船,不要中途放弃,要坚持,要自我修炼,不断成长!那么,起航吧~这道 Two Sum 的题目作为 LeetCode 的开篇之题,乃是经典中的经典,正所谓‘ 平生不识 TwoSum,刷尽 LeetCode 也枉然 ’,就像英语单词书的第一个单词总是 Abandon 一样,很多没有毅力坚持的人就只能记住这一个单词,所以通常情况下单词书就前几页有翻动的痕迹,后面都是崭新如初,道理不需多讲,鸡汤不必多灌,明白的人自然明白。
这道题给了我们一个数组,还有一个目标数target,让找到两个数字,使其和为 target,乍一看就感觉可以用暴力搜索,但是猜到 OJ 肯定不会允许用暴力搜索这么简单的方法,于是去试了一下,果然是 Time Limit Exceeded,这个算法的时间复杂度是 O(n^2)。那么只能想个 O(n) 的算法来实现,由于暴力搜索的方法是遍历所有的两个数字的组合,然后算其和,这样虽然节省了空间,但是时间复杂度高。一般来说,为了提高时间的复杂度,需要用空间来换,这算是一个 trade off 吧,但这里只想用线性的时间复杂度来解决问题,就是说只能遍历一个数字,那么另一个数字呢,可以事先将其存储起来,使用一个 HashMap,来建立数字和其坐标位置之间的映射,由于 HashMap 是常数级的查找效率,这样在遍历数组的时候,用 target 减去遍历到的数字,就是另一个需要的数字了,直接在 HashMap 中查找其是否存在即可,注意要判断查找到的数字不是第一个数字,比如 target 是4,遍历到了一个2,那么另外一个2不能是之前那个2,整个实现步骤为:先遍历一遍数组,建立 HashMap 映射,然后再遍历一遍,开始查找,找到则记录 index。代码如下:
C++ 解法一:
Java 解法一:
或者可以写的更加简洁一些,把两个 for 循环合并成一个:
C++ 解法二:
Java 解法二:
Github 同步地址:
#1
类似题目:
4Sum
3Sum Smaller
3Sum Closest
3Sum
Two Sum III - Data structure design
Two Sum II - Input array is sorted
参考资料:
https://leetcode.com/problems/two-sum/
https://leetcode.com/problems/two-sum/discuss/3/Accepted-Java-O(n)-Solution
https://leetcode.com/problems/two-sum/discuss/13/Accepted-C++-O(n)-Solution
LeetCode All in One 题目讲解汇总(持续更新中...)
(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)
微信打赏
Venmo 打赏
---|---
The text was updated successfully, but these errors were encountered: