2021-01-07 leetcode题解

Two Sum
题：给一个数组vector和一个数target，在数组中找到两个元素的和相加等于target，并返回这两个元素的下标。
解：用一个map记录元素的值和下标分别为key和value，用一个循环在访问每一个元素的时候先检查该i元素的compliment= target - vec[i]是否在map中，如果在则返回这两个下标，如果遍历结束都没找到，则不存在。
时间复杂度：O（N），空间复杂度：O（N）.

Add Two Numbers
题：给两个链表，每个链表的每个元素都是0-9的数字，求着两个链表加起来的和，返回一个新链表；
解：定义一个新链表，定义一个int sum表示这两个链表元素加起来的和，同时保留上一个进位（如果有的话），定义一个指向第三个链表的指针，把这个指针作为当前node的next，每次相加结束后生成一个新的node都加到第三个链表后面。
时间复杂度：O(N), 空间复杂度O(N).