【LeetCode】TwoSum、AddTwoNumbers

发表于 2017-11-14 更新于 2020-09-21 分类于 Algorithm

LeetCode小记

好久没写过题目了，思维都僵化了←_←，所以先找点简单些的题目找找感觉。
因为现在基本不会用到C/C++，所以使用Java来做。

题意 > 求数组内相加为目标值的两个数的下标

这题要做出来很简单，但是想优化一下时间复杂度就要思考思考了。第一反应只想到了用Map来存数和下标的键值对，考虑是不是排个序再取个目标值的一半，然后向两边加。但是这样实际上做了层排序，耗费了时间，如果有多个目标值而数组一致的话，可以考虑。当然这里就不是了。

正解：使用Map，来逐个存储数组的数，并在存储前检查Map内是否包含a与将要存储的数b，满足b + a = target，满足则返回a的下标和当前数的下标，否则存储b及下标，然后继续下一个数。

小结：这样省去了查找下标、查到结果以外的无用计算等等。

刚好就看到有这题，之前从里往外的算法，实现比较不简洁，看到题解什么的都是从外往里算的，当然这样比较好用while来写。

题意 > 两个正整数，用单向链表来倒叙表示，链表的每个节点代表数的一位，求相加后的数对应链表。

要点：相加进位，进位的值要加到下一个节点，最高位进位，两个数不同长度的补位

坑：1 + 9,9,9 = 0,0,0,1，这里多次进位

方法：我一开始用的递归实现，因为更好想一点吧（以前一定直接非递归的Orz），每个节点考虑，计算相加的结果，然后填入new的节点t，t的next递归调用传入两个节点对应的next，中间加上判空以及溢出计算就好了。
非递归也没有那么麻烦，只是用while来实现子节点的计算。