Two Sum

基础之基础，不多说了，肯定是要O(n)实现的，因为是未排序数组，还需要借助哈希表来存值了，下面是代码

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        store = {}

        for i in xrange(n):
            if target - nums[i] in store:
                return [store[target - nums[i]], i]
            store[nums[i]] = i

        return ''

Java版本

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> store = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (store.containsKey(target - nums[i])) {
                return new int[] {store.get(target - nums[i]), i};
            }
            store.put(nums[i], i);
        }
        return new int[2];
    }
}

Two Sum III

这道题无论如何，add或者find总有一个函数的时间复杂度要是O(n)（也许有平摊的方法？），那这里就只能trade off了，LC里面只有quick add的方法能通过

class TwoSum(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.checkList = {}
        self.numStore = []

    def add(self, number):
        """
        Add the number to an internal data structure..
        :type number: int
        :rtype: void
        """
        self.numStore.append(number)
        self.checkList.setdefault(number, 0)
        self.checkList[number] += 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.numStore:
            if value - num in self.checkList:
                if value - num == num and self.checkList[num] > 1:
                    return True
                if value - num != num:
                    return True

        return False


# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)