给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807
接下来给出上一个算法【两数之和】的答案：
public int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[j] == target - nums[i]) {return new int[] { i, j };}}}throw new IllegalArgumentException("No two sum solution");}
方法二：两遍哈希表
使用两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到哈希表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]）是否存在于哈希表中。（注意，该目标元素不能是 nums[i]nums[i] 本身）
public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {map.put(nums[i], i);}for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement) && map.get(complement) != i) {return new int[] { i, map.get(complement) };}}throw new IllegalArgumentException("No two sum solution");}
方法三：一遍哈希表
在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。
public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[] { map.get(complement), i };}map.put(nums[i], i);}throw new IllegalArgumentException("No two sum solution");}
注意：这道题本身不太严谨，如果使用hash表的方式，遇到[2,2,4,5]，target=4，这种数据就会有问题。题中应该加上数组内的元素不能重复。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-number
本文分享自微信公众号 - 自增程序员（javaipp）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
