[数据结构与算法]LeetCode 1.Two Sum-2.Add Two Numbers

1. 两数之和 Two Sum

方法一：暴力解法

枚举数组中的每一个数 x，在 x 后面的元素中寻找 target - x。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(n:=len(nums)):
            for j in range(i+1, n): # 从 i 后面找
                if nums[i] + nums[j] == target:
                    return [i,j]
        return []

• 时间复杂度：O(N²)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：O(1)。

方法二：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]: 
        for i, element in enumerate(nums):
            #if target-element in nums[i+1:]:
            #    return [i,nums.index(target-element,i+1)]
            try:
            	j = nums.index(target-element,i+1)
            	return i, j
            except:
            	pass

方法三：哈希表

创建一个字典，对于每一个 x，首先查询哈希表中是否存在 target - x，如果存在，则返回结果，否则将 x 插入到哈希表中。
注意：方法一是对于 x，从后面找 target-x；方法二是先把 target-x 和它的下标放到字典中，然后对后面的 x 在字典中找 target-x。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, right in enumerate(nums):
            left = target - right
            if left in hashtable:
                return [hashtable[left], i]
            hashtable[nums[i]] = i
        return []

• 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
• 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

2. 两数相加 Add Two Numbers

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。如果当前两个链表处相应位置的数字为 n1，n2，进位值为 carry，则它们的和为 n1 + n2 + carry；其中，答案链表处相应位置的数字为 (n1 + n2 + carry) % 10，而新的进位值为 （n1 + n2 + carry）// 10。

此外，如果链表遍历结束后，有 carry = 1，还需要在答案链表的后面附加一个节点，节点的值为 carry。

小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点 head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        l3 = cur = ListNode() # l3 和链表
        carry = temp = 0

        while carry or l1 or l2:
            temp = carry 
            
            # 累加 进位 l1.val l2.val
            if l1: l1, temp = l1.next, l1.val + temp
            if l2: l2, temp = l2.next, l2.val + temp

            carry, temp = divmod(temp, 10)
            cur.next = cur = ListNode(temp)
        
        return l3.next

LISTNODE 的 PYTHON 实现

class Node:
    def __init__(self):
        self.val = None
        self.next = None

class Node_handle():
    def __init__(self):
        self.cur_node = None
　　# 查找
    def find(self,node,num,a = 0):
        while node:
            if a == num:
                return node
            a += 1
            node = node.next
　　# 增加
    def add(self,data):
        node = Node()
        node.val = data
        node.next = self.cur_node
        self.cur_node = node
        return node
　　# 打印
    def printNode(self,node):
        while node:
            print ('\nnode: ', node, ' value: ', node.val, ' next: ', node.next)
            node = node.next
　  # 删除
    def delete(self,node,num,b = 1):
        if num == 0:
            node = node.next
            return node
        while node and node.next:
            if num == b:
                node.next = node.next.next
            b += 1
            node = node.next
        return node
　　# 翻转
    def reverse(self,nodelist):
        list = []
        while nodelist:
            list.append(nodelist.val)
            nodelist = nodelist.next
        result = Node()
        result_handle =Node_handle()
        for i in list:
            result = result_handle.add(i)
        return result

if __name__ == "__main__":
    l1 = Node()
    ListNode_1 = Node_handle()
    l1_list = [1, 8, 3]
    for i in l1_list:
        l1 = ListNode_1.add(i)
    ListNode_1.printNode(l1)
    l1 = ListNode_1.delete(l1,0)
    ListNode_1.printNode(l1)
    l1 = ListNode_1.reverse(l1)
    ListNode_1.printNode(l1)
    l1 = ListNode_1.find(l1,1)
    ListNode_1.printNode(l1)