1. Two Sum (HashTable) 20.1.28 Easy

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].

Solution no.1: ---------------------- ok for normal case, but failed because of "Time Limit Exceeded" : 运算时间太长，需要优化
--------------------- This code's time complexity is o(n^2), as you know, N will bigger than 16000, so this complexity is unacceptable
--------------------- As for the space complexity, a recursive function's memory complexity is O(recursion depth) => O(2)
class Solution(object):
    def twoSum(self, nums, target):
        res = []
        self.twoSum_help(nums, target, res, [], 0)
        return res
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
    def twoSum_help(self, nums, target, res, path, startidx):
        if len(path) == 2 and target == 0:
            res.extend(path[:])
        if len(path) < 2:
            for i in range(startidx, len(nums)):
                path.append(i)
                self.twoSum_help(nums, target - nums[i], res, path, i + 1)
                path.pop()
                
Solution no.2: ------------------------------------- Brute Force O(n^2) time, O(1) space
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

Solution no.3: -------------------------------- Hashtable
------------------------------------------------ O(n) T, O(n) S
class Solution(object):
    def twoSum(self, nums, target):
        HashTable = {}                                # Create a dictionary that record the key:value pair
        for i, num in enumerate(nums):                # for example: dic = {2:0, 7:1, 11:2, 15:3}, key:value
            if target - num in HashTable:             # IMPORTANT !!!!!!!!!!!!!!!!!!!!!!!! We MUST first check if there exist any pair
                                                      # before append num into the HashTable !!!!!!!!!!!!!!!!!!!!!!!!!!
                                                      # Otherwise, the HashTable will keep append new item without return anything
                                                      # for cases like [2, 7, 11, 15] 9
                                                      # Also, we cannot write code as below WITHOUT check ( )
                                                      # if not num in HashTable:
                                                      #     HashTable[num] = i
                                                      # if target - num in HashTable (and i != HashTable[target - num]):
                                                      #     return [i, HashTable[target - num]]
                                                      # key in dic
                return[i, HashTable[target - num]]    # value in dic can only be assess by dic[key]
                                                      # dic[key] -> value. key is like a special index
            else:
                HashTable[num] = i

Solution no.4? Two Pointers? 
Since this question asks us to return the original index instead of the item value, two pointers is not applicable here.


Java Version no.1:
class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return null;
        }
        Map<Integer, Integer> hashMap = new HashMap<>();
        for(int i = 0; i < nums.length; i ++) {
            if(hashMap.containsKey(target - nums[i])) {
                return new int[] {hashMap.get(target - nums[i]), i};
            } else {
                hashMap.put(nums[i], i);
            }
        }
        return null;
    }
}

Java version no.2:
class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        
        Map<Integer, Integer> hashMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i ++) {
            if (!(hashMap.containsKey(nums[i]))) {
                hashMap.put(nums[i], i);
            }
            if (hashMap.containsKey(target - nums[i]) && i != hashMap.get(target - nums[i])) {
                return new int[] {hashMap.get(target - nums[i]), i};
            }
        }
        
        return null;
    }
}