一个easy题目的长篇大论
上篇提到了codewars的一道算法题，这次是著名算法网站leetcode的介绍，这两个网站区别就以后在说了。因为以前也在leetcode玩过，但是没系统的，没持久的进行过，真的只是玩玩，现在还是希望自己能够熟悉算法的一些内容，虽然不是算法科班出身，但是掌握常用算法以及思路还是绝对必要的。
由于是leetcode开篇之作，所以也拿网站第一道的easy类别题来实例，题目地址two sum 任务为：给定一个数组，一个值，让你求解数组两个元素的index，让这两个元素和为指定的值。 题目非常非常的简短和简单，但是千万不要上来就干就提交，不然红字就将等待着你(我就是啊…)。因为既然是算法题一定对时间复杂度是有要求的，所以一定要尽可能的去写最优解。 请相信我，请不要觉得这个是网站的第一个入门级easy题目就小看它，真的不要有这种心态，相反，经过再次（为什么说再次呢）仔细做下来，对这道题真的是感觉收获颇丰。没做过这个题的同学建议请忽略下文，一定要自己上手去试试先。
好了，仔细看题目，其实已经减少了其他很多无关的情况，因为必然存在一个正确解，所以只需要去考虑怎么把这个解给弄出来就行了。既然数组中的两个值必然会相加等于一个固定值，那直接对数组循环就行了，但是答案要求的index，所以直接对数组的index循环，每循环一个数，就去判断这个数组是不是存在相差的那个值就行了。直接上ruby代码：
def two_sum(nums, target)
nums.each_index do |i|
id = nums.rindex(target - nums[i]).to_i
return [i, id] if id > i
end
end
虽然用python或者没接触过ruby的同学可能会不熟悉，但是这里先只讲解思路。ruby的代码去掉格式相关的end，实际核心就是一行，但是这一行或者相关几行其实还是蕴藏着很多的考虑。 首先each_index方法是对index的循环，因为结果要求我们提交的是index，然后循环中的核心函数是rindex，也就是从反方向(为什么要反方向搜?)去搜寻target - nums[i]的index，最后需要对这个返回值进行to_i，也就是整数化，下面讲下为什么要做这些。
- 假设为题目的case，数组[2,7,11,15]，target是9，那么我们对数组循环到第一个2的时候，target-nums[0]就是7，而这个7正好通过rindex函数是有正确有效的返回值的，所以，对于case而言，这个数组我们进行了第一次迭代就直接return结束了，非常高效、准确,整个求解的复杂度只有O(n)。
- 而return语句里有
if id > i, 是为什么呢？因为假设有[2,6,7]和target=4的时候，也就是target-num[i]和num[i]相等的时候，且数组只有一个target/2的值的情况下，如果不加id>i，就会得出错误结果，比如本条假设就会直接得出[0,0]的错误结果,id > i 保证的就是不能让第二个差值的index是第一个值的index。因为题目规定，数组元素不能使用两次。但是rindex对于数组有两个0.5 target的时候是准确无误的，比如[2,2,5],target=4，就能一次计算出正确结果[0，1]。本题目隐藏的最大陷阱也就是这种情况，即target是偶数，且数组有1个或者2个0.5 target的情况，如果没考虑到这点就是直接gg。 - 当rindex在数组找不到匹配的值时，就会产生nil值，因为我们后续接了to_i整数化函数，所以找不到情况下id的值通通为0，必然就无法return了，直到循环到符合结果的值为止
ruby通过巧妙的使用rindex和to_i函数，优雅的一行就解决了所有的问题，不愧是为了编程高兴而生的语言。
至于python，貌似因为list没有rindex函数(或者是我不知道？),而通过reverse和index之类的间接去实现又感觉多了次运算，在这种情景下是没有必要的，所以按照ruby的这种思路是没办法完全重现的。
提交后可以看到此次solution跟其他人的比较，包括时间，内存请求之类的，发现本次解大概是260ms左右，看看其他人的，只有30-40ms，点开一看：
def two_sum(nums, target)
hsh = {}
nums.each_with_index do |num, index|
s = target - num
if hsh[s]
return [hsh[s], index]
end
hsh[num] = index
end
end
巧妙的用了hash来实现查询是否存在target - num的目的，这确实是一个最优解，思路也简单。因为本人在在码代码的时候都习惯使用单一的数据结构，看来这确实是一个不好的习惯，因为不同的数据结构是适合不同任务和目的的，一定要搭配起来，而且从这里的结果看来，hash的使用在速度上是比数组要快很多的，而且逻辑设计和实现起来也容易多了，像用python如果还是按照我自己的思维用数组去解决的话那就是一件相对复杂的事情了。
好了，既然数组不好做，那么我们用hash的逻辑用python再次实现一次把：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
h = {}
for i in range(len(nums)):
if (target - nums[i]) in h:
return [h[target-nums[i]], i]
else:
h[nums[i]] = i
嗯，虽然谈不上优雅，但是只花了68ms，跟大佬们挤在一起了，哈哈！ 通过这个简单问题，我还是收获了不少，各位道友呢！
###后记 其实在最开始我写的ruby代码虽然通过了所有test，但是后来想想应该还是不对的，比如拿test数据来说nums = [2, 7, 11, 15], target = 9,是没问题的，但是假如数据变成了num = [2, 7, 7, 15], target = 9,那么上述代码的结果将得到[0,2],而实际正确答案应该是[0，1],所以其实上述代码只有在相差值只有1个的情况下才是正确的，超过1个就是错误的代码了，而题目并没有说明数据是只有1个的，所以理论上，上述通过测试的代码其实是不正确的，从这里也可以看出，leetcode的test的数据是不全面的，可能并没有随机产生足够多的test样本数据。真正正确且最优的解，还是用hash的方式，从左到右扫描一遍就OK了，真的是简单、粗暴、效率。