1. Two Sum

def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return []
        d = {}
        for i, num in enumerate(nums):
            if target - num in d:
                return [d[target - num], i]
            d[num] = i

167. Two Sum II - Input array is sorted

def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        l, r = 0, len(numbers) - 1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target:
                return [l + 1, r + 1]
            elif s < target:
                l += 1
            else:
                r -= 1

170. Two Sum III - Data structure design

class TwoSum(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {}

    def add(self, number):
        """
        Add the number to an internal data structure..
        :type number: int
        :rtype: void
        """
        self.d[number] = self.d.get(number, 0) + 1

    def find(self, value):
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        :type value: int
        :rtype: bool
        """
        for num in self.d:
            if value - num in self.d and (value - num != num or self.d[num] > 1):
                return True
        return False

653. Two Sum IV - Input is a BST

def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        if not root: return False
        queue, vals = [root], set()
        for i in queue:
            if i.val in vals: return True
            vals.add(k - i.val)
            if i.left: queue.append(i.left)
            if i.right: queue.append(i.right)
        return False

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        nums = []
        self.inorder(root, nums)
        l, r = 0, len(nums) - 1
        while l < r:
            s = nums[l] + nums[r]
            if s == k:
                return True
            if s < k:
                l += 1
            else:
                r -= 1

        return False

    def inorder(self, root, nums):
        if not root: return
        self.inorder(root.left, nums)
        nums.append(root.val)
        self.inorder(root.right, nums)