Optimize Two Sum Problem: A Comprehensive Guide to Add Two Numbers

时间：11-13 神话故事提交错误

其实Optimize Two Sum Problem: A Comprehensive Guide to Add Two Numbers的问题并不复杂，但是又很多的朋友都不太了解，因此呢，今天小编就来为大家分享Optimize Two Sum Problem: A Comprehensive Guide to Add Two Numbers的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！

总之，问题需要用算法来解决，而这些算法的实现就在于对数据结构的掌握。

1、Two sum

题目：给定一个整数数组和一个特定目标，该目标是通过将数组中的元素相加来获得的。要求返回这两个元素在数组中的索引。

可以假设这个数组中只有一个解，并且不能使用相同的元素。

例子：

给定nums=[2, 7, 11, 15]，目标=9，

因为nums[0] + nums[1]=2 + 7=9，

return [0, 1] 是我刚才回答的第一个问题，我遇到了几个陷阱：如果数组是[3, 3]，那么返回的索引list.index(3) 是相同的。 ····如果使用两个for循环，时间复杂度为O(n2)。超过时间限制。

解题技巧：如果不能使用索引，则使用字典进行索引。如果不能使用两个for 循环，请使用加数作为值，将加数作为键。

解：dict_nums={}

#Dictionary 使用加数作为键

对于范围内的n (len(nums)):

m=目标数量[n]

#如果m已经在字典中，则说明已经存储在字典中的列表中已经有一个符合条件的加数。该加数的关键是索引值，并得到解。

如果m 在dict_nums: 中

返回dict_nums[m],n

否则：

#如果m不在字典中，则以m为key，索引值n为value，存入字典中供以后使用。

dict_nums[nums[n]]=n

2. Add Two Numbers

题目：给定两个非空链表，代表两个正数，数字按倒序存储在链表中，链表中的每个节点存储一个单独的数字。要求将这两个数字相加，并以相同的形式（倒序）返回链表。

可以假设，除了0 本身之外，数字不以0 开头。

例子：输入： (2 -4 -3) + (5 -6 -4)

输出： 7 -0 -8

说明： 342 + 465=807.需要注意的坑：1. 两个数字的长度不同。 2. 一个列表是空的。 3. 两个数字都是0。

用到的技巧：1. 取余：如果n小于10，则n%10=n2。取整数：如果n小于10，则n//10=0

可以使用以上两种方法来查找组成数字（807）的每个元素（8/0/7）。

余数=x % 10

x=x//10

807//10=80，下次余数为0，下次余数为8。

我的做法：1、依次读取链表，用while将个位乘以10，然后将百位乘以10，表达链表中的数字。 2. 添加上面表示的两个链表。获得总和后，按照上述技术查找组成该数字的每个元素并获得列表。 3、因为链表需要倒序存储，所以将上一步得到的链表倒转后，按照向链表添加节点的方法，依次添加元素即可得到链表。我的缺点：1.因为我考虑到不能踏入“两个数不相等”的陷阱，所以连续用了好几个while。事实上，你可以用or 连接两个数字。当一个为空且另一个为真时，while 循环可以继续。 2、因为我们考虑到不应该陷入“单个数字相加可能包含进位”的陷阱，所以我们将两个数字分开表示，然后将它们相加，然后返回链表。实际上是可以再加一个变量carry表示进位符。这样，你可以将各个数字相加，当你想到计算下一位数字的方法时，只需添加进位即可。为了解题方便，可以多加变量从头添加节点到链表的步骤（头已经存在）

1. 构建新节点

cur_new=ListNode(进位%10)

2、新节点的next指向原链表的头部。

cur_new.next=当前

3. 如果头节点消失了，则将新节点设置为头节点。

cur_head=cur_new

比较好的改进：def addTwoNumbers(self, l1, l2):

dummy=cur=ListNode(0)#定义一个表头

进位=0

而l1或l2或进位：#

如果l1:

进位+=l1.val