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;
}
};
# @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
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 需要使用 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")
}
}
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()
}
}