You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

#### 思路

• 时间复杂度 O(maxlen)
• 空间复杂度 O(maxlen)

• 执行用时: 0 ms
• 内存消耗: 2.1 MB

1. 链表
2. 大数运算

# 0001. Two Sum

#### 0001. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

#### 思路

1. 暴力 时间复杂度 O(n2) 空间复杂度 O(1)
2. 哈希 时间复杂度 O(n) 空间复杂度 O(n)）
3. 排序再查找 时间复杂度 O(nlogn) 此题返回下标不可行，相似题可行

#### 暴力两次循环

``impl Solution{  pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {let len = nums.len();for i in 0..len {for j in i+1..len {   if nums[i] + nums[j] == target {   return vec![i as i32, j as i32];}}}   vec![]   }}``

• 执行用时: 40 ms
• 内存消耗: 2.1 MB

for循环两次，判断是否相等。

``impl Solution{    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {                for(i, num_i) in nums.iter().enumerate()         {            for (j, num_j) in nums.iter().enumerate()            {                if i != j  && num_i + num_j == target                {                    return vec![i as i32, j as i32]                }             }        }      vec![]    }}``

• 执行用时: 76 ms
• 内存消耗: 2 MB

#### HashMap

``use std::collections::HashMap;impl Solution {pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {let mut map = HashMap::with_capacity(nums.len());for(index,num) in nums.iter().enumerate() {if let Some(&find) = map.get(&(target-num)) {return vec![find as i32, index as i32];}map.insert(num,index);}vec![]}}``

• 执行用时: 0 ms
• 内存消耗: 2.3 MB

#### 问题与优化思路

X Sum的解题思路主要是把它转化为(X-1)Sum，最后成为2Sum问题，得到最后的答案。

#### 题型与相似题

1. 数组
2. 哈希表

1. Two Sum II – Input array is sorted
2. Two Sum III – Data structure design
3. 3 Sum
4. 3 Sum Smaller
5. 3 Sum Closet
6. 4 Sum

two_sum