Leetcode 第1题：能否找到两个数，它们的和为特定值？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1226个文字，预计阅读时间需要5分钟。
Leetcode 1. Two Sum 前言：本篇是 Leetcode 刷题第一篇，对于大部分人来说，Two Sum 都是刷题的起点，就像单词书中的 abandon。至于后续会不会 abandon，拭目以待。整个 Leetcode 刷题系列，我计划使用。
Leetcode 1. Two Sum
前言本篇是 Leetcode 刷题第一篇，对于大部分人来说 Two Sum 都是刷题的开端，就像单词书的 abandon 。至于后续会不会 abandon，拭目以待。
整个 Leetcode 刷题系列我准备使用多种语言来写。我的第一份工作就是全栈(干)工程师，刚从学校毕业到上海找到一家小公司实习，然后留在那。小公司你们懂的，一人身兼数职，什么都会一点。我是从 Ruby on Rails 入门开发的，说实话，我虽然是计算机专业的，在去公司实习之前真没听过 Ruby 语言，由此可见这么语言有多冷门(是我太孤陋寡闻了)。Ruby 这门语言非常有特色了，靠着 Ruby on Rails 一直不温不火的发展。RoR 框架对新手并不是很友好，或者说学习路线陡峭。作为一个新人，对 MVC 框架不熟悉，新建一个项目就有一大堆文件夹+文件，哪像 PHP，初学者可以单个文件走天下。 幸好 RoR 框架有完善的 tutorial 和友好的社区，Ruby China 社区应该是中国最好的技术论坛之一(之一也许可以去掉)。
对 Ruby 和 RoR 我有种特殊的感情，它给我的感觉是优雅，高效。我自建的站也全部采用 RoR，RoR 的开发效率是毋庸置疑的。之前有个小伙伴在我的网站下留言能不能写用 Ruby 刷 Leetcode 的笔记， Leetcode 不少题甚至没有人用 Ruby 写题解。其实我早就想写了，一直有各种事情耽误了，现在有点时间可以写一写了，也借此为 Ruby 的推广稍稍添砖加瓦吧。(太不要脸了，根本无足轻重)
之前在公司也开发过 iOS 应用，也写了不少 OC 和 Swift 代码，后面渐渐就不写了，语法内容也基本忘得差不多了，借着刷题的机会慢慢捡起来。现在我在学校做深度学习的相关内容，主要用 C++ 和 Python，所以这次刷题至少使用了四种语言 C++、Ruby、Python 和 Swift。
原谅我这么多碎碎念。。。
对于第一题最先想到的算法是用两层循环遍历数组，nums[j]==target-nums[i] 。时间复杂度为 \(O(n^2)\)。算法主要浪费在找到 target-nums[i] 这个数，找这个数的时间复杂度为 \(O(n)\)，即遍历整个数组。
我们可以使用哈希表存储每个数及其对应的下标，这样就可以在 \(O(1)\) 时间内找到 target-nums[i]，整个算法时间复杂度为 \(O(n)\)。
由于这道题比较简单，也没必要写什么题解了，大家直接看代码吧，
C++C++ 使用 unordered_map 来存储键值对。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> index;
vector<int> result;
int nSize = nums.size();
int residue;
for(int i = 0; i < nSize; i++) {
residue = target - nums[i];
if(index.find(residue) != index.end()) {
result.push_back(index[residue]);
result.push_back(i);
return result;
}
index[nums[i]] = i;
}
return result;
}
};
Ruby
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
hs = {}
nums.each_with_index do |num, idx|
subt = target - num
if hs.has_key?(subt)
return [hs[subt], idx]
end
hs[num] = idx
end
end
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
Swift
Swift 需要使用 enumerated() 获取数组值和下标，可参照 Ruby 的 each_with_index。Swift 和 Ruby 语法相较其他语言有很多不同，刷题时可以领略不同风格的语言。
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict = [Int: Int]()
for (i, num) in nums.enumerated() {
if let lastIndex = dict[target - num] {
return [lastIndex, i]
}
dict[num] = i
}
fatalError("No valid outputs")
}
}
Rust
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::new();
for i in 0..nums.len() {
if let Some(val) = map.get(&(target - nums[i])) {
if i != *val {
return vec![i as i32, *val as i32];
}
}
map.insert(nums[i], i);
}
Vec::new()
}
}
本文共计1226个文字，预计阅读时间需要5分钟。
Leetcode 1. Two Sum 前言：本篇是 Leetcode 刷题第一篇，对于大部分人来说，Two Sum 都是刷题的起点，就像单词书中的 abandon。至于后续会不会 abandon，拭目以待。整个 Leetcode 刷题系列，我计划使用。
Leetcode 1. Two Sum
前言本篇是 Leetcode 刷题第一篇，对于大部分人来说 Two Sum 都是刷题的开端，就像单词书的 abandon 。至于后续会不会 abandon，拭目以待。
整个 Leetcode 刷题系列我准备使用多种语言来写。我的第一份工作就是全栈(干)工程师，刚从学校毕业到上海找到一家小公司实习，然后留在那。小公司你们懂的，一人身兼数职，什么都会一点。我是从 Ruby on Rails 入门开发的，说实话，我虽然是计算机专业的，在去公司实习之前真没听过 Ruby 语言，由此可见这么语言有多冷门(是我太孤陋寡闻了)。Ruby 这门语言非常有特色了，靠着 Ruby on Rails 一直不温不火的发展。RoR 框架对新手并不是很友好，或者说学习路线陡峭。作为一个新人，对 MVC 框架不熟悉，新建一个项目就有一大堆文件夹+文件，哪像 PHP，初学者可以单个文件走天下。 幸好 RoR 框架有完善的 tutorial 和友好的社区，Ruby China 社区应该是中国最好的技术论坛之一(之一也许可以去掉)。
对 Ruby 和 RoR 我有种特殊的感情，它给我的感觉是优雅，高效。我自建的站也全部采用 RoR，RoR 的开发效率是毋庸置疑的。之前有个小伙伴在我的网站下留言能不能写用 Ruby 刷 Leetcode 的笔记， Leetcode 不少题甚至没有人用 Ruby 写题解。其实我早就想写了，一直有各种事情耽误了，现在有点时间可以写一写了，也借此为 Ruby 的推广稍稍添砖加瓦吧。(太不要脸了，根本无足轻重)
之前在公司也开发过 iOS 应用，也写了不少 OC 和 Swift 代码，后面渐渐就不写了，语法内容也基本忘得差不多了，借着刷题的机会慢慢捡起来。现在我在学校做深度学习的相关内容，主要用 C++ 和 Python，所以这次刷题至少使用了四种语言 C++、Ruby、Python 和 Swift。
原谅我这么多碎碎念。。。
对于第一题最先想到的算法是用两层循环遍历数组，nums[j]==target-nums[i] 。时间复杂度为 \(O(n^2)\)。算法主要浪费在找到 target-nums[i] 这个数，找这个数的时间复杂度为 \(O(n)\)，即遍历整个数组。
我们可以使用哈希表存储每个数及其对应的下标，这样就可以在 \(O(1)\) 时间内找到 target-nums[i]，整个算法时间复杂度为 \(O(n)\)。
由于这道题比较简单，也没必要写什么题解了，大家直接看代码吧，
C++C++ 使用 unordered_map 来存储键值对。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> index;
vector<int> result;
int nSize = nums.size();
int residue;
for(int i = 0; i < nSize; i++) {
residue = target - nums[i];
if(index.find(residue) != index.end()) {
result.push_back(index[residue]);
result.push_back(i);
return result;
}
index[nums[i]] = i;
}
return result;
}
};
Ruby
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
hs = {}
nums.each_with_index do |num, idx|
subt = target - num
if hs.has_key?(subt)
return [hs[subt], idx]
end
hs[num] = idx
end
end
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
Swift
Swift 需要使用 enumerated() 获取数组值和下标，可参照 Ruby 的 each_with_index。Swift 和 Ruby 语法相较其他语言有很多不同，刷题时可以领略不同风格的语言。
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict = [Int: Int]()
for (i, num) in nums.enumerated() {
if let lastIndex = dict[target - num] {
return [lastIndex, i]
}
dict[num] = i
}
fatalError("No valid outputs")
}
}
Rust
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::new();
for i in 0..nums.len() {
if let Some(val) = map.get(&(target - nums[i])) {
if i != *val {
return vec![i as i32, *val as i32];
}
}
map.insert(nums[i], i);
}
Vec::new()
}
}