1. 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.1 双重循环

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res = []
        for i in range(0,len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j] == target:
                    res.append(i)
                    res.append(j)
                    return(res)

• 注意循环的起始点和终点，尤其是前后有关系的
• 双重循环也要考虑下区间
• append只能一项一项加

Runtime: 5868 ms, faster than 14.79% of Python3 online submissions for Two Sum.
Memory Usage: 13.8 MB, less than 71.39% of Python3 online submissions for Two Sum.

1.2 哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
python中的dict类型就是哈希表的原理，存储方式是key-value，通过键来快速的访问value，字典在访问操作上时间复杂度为O(1)。

class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       res = []
       dict_nums = {}
       for i in range(0,len(nums)):
           if (target-nums[i]) in dict_nums.keys():
               res.append(i)
               res.append(dict_nums[target-nums[i]])
           else:
               dict_nums[nums[i]] = i
       return(res)

• 啥时候建表比较重要
• 考虑特殊情况：nums里有两个一样的元素，或者某个元素两倍得target，判断条件应该怎么写
• 用空间换时间
• 因为是索引查询速度快，所以把value放在索引上

Runtime: 44 ms, faster than 92.43% of Python3 online submissions for Two Sum.
Memory Usage: 14.9 MB, less than 13.95% of Python3 online submissions for Two Sum.

1.3 先排序再两端逼近

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res = []
        nums2=list(map((lambda x: x),nums))
        nums2.sort()
        i=0
        j=len(nums)-1
        if j==0:
            return([])
        while(i<j):
            if (nums2[i]+nums2[j])>target:
                j=j-1
            elif (nums2[i]+nums2[j])<target:
                i=i+1
            elif (nums2[i]+nums2[j])==target:
                res.append(nums.index(nums2[i]))
                res.append(nums.index(nums2[j]))
                return(res)
        return([])

• lambda函数的用法：输入和输出，注意要转list；
• map函数：有交互时用；
• sort函数
• 这个方法在有两项相同数的时候不适用，比如[3,3], 6, 鉴于index函数会返回最近的符合条件的值，所以不能用。

2. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i,j=0,len(numbers)-1
        while(i<j):
            s=numbers[i]+numbers[j]
            if s>target:
                j=j-1
            elif s<target:
                i=i+1
            else:
                return([i+1,j+1])
        return([])

Runtime: 56 ms, faster than 96.96% of Python3 online submissions for Two Sum II - Input array is sorted.
Memory Usage: 13.3 MB, less than 100.00% of Python3 online submissions for Two Sum II - Input array is sorted.

3. Two Sum IV - Input is a BST

3.1 遍历之后列表查找

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        ls_value = []
        def preorder(root):
            if root == None:
                return()
            ls_value.append(root.val)
            preorder(root.left)
            preorder(root.right)
        preorder(root)
        ls_value.sort()
        i,j=0,len(ls_value)-1
        while(i<j):
            s=ls_value[i]+ls_value[j]
            if s==k:
                return(True)
            elif s<k:
                i+=1
            else:
                j-=1
        return(False)

先前序遍历，结果存在一个list里，然后两端逼近。

Runtime: 92 ms, faster than 27.45% of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: 15.1 MB, less than 100.00% of Python3 online submissions for Two Sum IV - Input is a BST.

时间复杂度比较高，但是节约空间。

3.2 遍历的过程中用in匹配

class Solution:
    def findTarget(self, root: 'TreeNode', k: 'int') -> 'bool':
        s = set()
        def helper(root, k):
            if not root: return False
            if k - root.val in s: return True
            s.add(root.val)
            return(helper(root.left, k) or helper(root.right, k))
        return helper(root, k)

Runtime: 76 ms, faster than 72.03% of Python3 online submissions for Two Sum IV - Input is a BST.
Memory Usage: 15.2 MB, less than 100.00% of Python3 online submissions for Two Sum IV - Input is a BST.
好处是不用完成整个遍历就可以return了，所以节约时间。