LeetCode介绍
LeetCode是算法练习、交流等多功能网站，感兴趣的同学可以关注下（老司机请超车）。页面顶部的Problems菜单对应算法题库，附带历史通过滤、难易程度等信息。
未来计划
打算用Kotlin语言，按照从易到难的顺序有选择地实现LeetCode库中的算法题，考虑到Kotlin的学习与巩固、算法的思考与优化，争取一星期完成一篇文章（每篇只总结一题，可能偷偷做了后面的好几题^_^）。
当然，除了单纯地用kotlin实现外，还会指出一些容易忽略的坑，并对结果进行更深一层的分析。
编码测试
点击标题就会进入具体的题目界面，包括描述、编码区、运行/提交按钮、参考方案、讨论等。
这次就先选择第一题：给定一个整数型的数组nums和一个目标值target，要求编码实现计算出两个数组下标index1和index2，使得两个下标对应的元素和等于目标值，即nums[index1]+nums[index2]=target。
由于描述中有提到，可以假设每个输入都会有一个靠谱的答案，且同一个元素不能用两次（即不允许出现[2, 2]这样的结果），所以实现的时候可以不用太担心有没有答案或什么异常之类的情况，之后的编码中只会象征性地给出没有结果时的异常处理。
方案1，两层for循环
class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
..nums.size - ) {
..nums.size - ) {
if (nums[j] == target - nums[i]) {
return kotlin.intArrayOf(i, j)
}
}
}
throw IllegalArgumentException("No two sum solution")
}
}
上述代码中for循环用了..，是会包含最后一个元素的，即范围取[start, end]。和..效果相同的有rangeTo，类似的还有until（差别在于范围取[start, end)，具体用法感兴趣的同学尝试并做比较）。
在LeetCode上运行会提示正确性与耗时等信息，本文只给出本地电脑上IntelliJ IDEA的运行情况（不存在LeetCode运行时可能有网速等外在因素的干扰）。
测试案例（下同）：
fun main(args: Array<String>) {
var start = System.currentTimeMillis()
println(, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
), ).asList())
var end = System.currentTimeMillis()
println(end - start)
}
关于耗时，建议采用多次运行后再取平均，这里留给大家发挥想象。最好在一个稳定的环境下测试，且耗时是相对的（相同环境下对不同算法的结果进行对比，环境变化可比性就意义不大了）。
输出：
运行多次，发现耗时31ms居多，有时会是47ms，偶尔会是67ms等。
方案2，Map初始添加
class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
val mapA = mutableMapOf<Int, Int>()
..nums.size - ) {
mapA.put(nums[i], i)
}
..nums.size - ) {
var value = target - nums[i]
if (mapA.containsKey(value) && mapA.get(value) != i ) {
return kotlin.intArrayOf(i, mapA.get(value)!!)
}
}
throw IllegalArgumentException("No two sum solution")
}
}
消除了两层循环，多用了一个数组元素的空间，本意是打算用空间换时间。
方案3，Map过程添加
class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
val mapA = mutableMapOf<Int, Int>()
..nums.size - ) {
var value = target - nums[i]
if (mapA.containsKey(value)) {
return kotlin.intArrayOf(mapA.get(value)!!, i)
} else {
mapA.put(nums[i], i)
}
}
throw IllegalArgumentException("No two sum solution")
}
}
针对mapA的元素添加过程做了优化，不是像方案2中那样一开始就将数组元素全部进行映射，而是边查找边添加。
结果分析
注意点1，耗时情况
后面两种方案没有给出输出结果，原因是对于耗时来说，三种方案是差不多的。这就有疑问了，后两种利用了Map映射机制，可能在空间上确实增加了，但是循环才是耗时主要因素，为什么时间并没有减少呢？
遇到这种情况，就不建议百度或者谷歌了，不为别的，就因为源码最靠谱。
代码中是通过mutableMapOf建立mapA变量的，找下去，在Maps.kt中：
public inline fun <K, V> mutableMapOf(): MutableMap<K, V> = LinkedHashMap()
线索LinkedHashMap，找下去，在TypeAliases.kt中：
@SinceKotlin("1.1") public typealias LinkedHashMap<K, V> = java.util.LinkedHashMap<K, V>
用到了类型别名。正如Kotlin的自我介绍，其和Java及JVM是很亲密的。线索java.util.LinkedHashMap，找下去，在LinkedHashMap.java中：
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
可以看到Kotlin中containsKey最终调用了Java中的getNode，真相就在下面：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
&&
(first = tab[(n - ) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
代码第11-15行，其实还是用到了遍历。问题的答案就有解了，Map+while耗时和for+for差别不大，前者代码更简洁，后者不需额外空间。
那么，有没有更好的方案呢？欢迎同学们提出，大家一起讨论、学习。
注意点2，Map映射的坑
LeetCode或者其他平台的测试案例也是随机的，有时候并不会发现代码中的潜在问题。
比如上述案例目标值是542，三种方案结果都是一致的[28, 45]。如果目标值改为1093，即数组的第一、二个元素下标[0, 1]是期望结果，但是第二种方案却是[0, 40]，而其他两种方案正常。
问题就出在其所有元素值是初始添加的，来看其中这一段代码：
..nums.size - ) {
mapA.put(nums[i], i)
}
对于Map映射，put操作当key不存在时进行添加，否则进行再赋值。所以当数组元素存在相同的值时，最后求出的下标值就会是最后一个，而不是第一个。
改进方案是在put操作前进行key的存在判断：
..nums.size - ) {
if (!mapA.containsKey(nums[i])) {
mapA.put(nums[i], i)
}
}