Q1 Two Sum

Two sum

Question

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

Approach 1: Brute Force

The brute force approach is simple. Loop through each element xx and find if there is another value that equals to target.

class Solution(object):
    def twoSum(self, nums, target):
        results = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    # if nums[i] not in results:
                        results.append(i)
                    # if nums[j] not in results:
                        results.append(j)
        return results

if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    target = 9
    answer=Solution()
    results=answer.twoSum(nums, target)
    print(results)

---

Approach 2: Two-pass Hash Table

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

We reduce the look up time from O(n) to O(1) by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say "near" because if a collision occurred, a look up could degenerate to O(n) time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. In the first iteration, we add each element's value and its index to the table. Then, in the second iteration we check if each element's complement (target - nums[i]) exists in the table. Beware that the complement must not be nums[i] itself!

The codes in some blogs are not preciseness enough. Here gives my Python code:

class Solution(object):
    def twoSum(self, nums, target):
        Hashmap = dict()
        results = []
        # 建立Hash表
        for i in range(0, len(nums)):
            Hashmap[nums[i]] = i #键是数值，值是序号
        # 查表
        for i in range(0, len(nums)):
            complement = target - nums[i]
            if complement in Hashmap and Hashmap[complement] != i:
            # 确认target不等于同一个元素乘以2
                if (not(set([i,Hashmap[complement]])<set(results) or [Hashmap[complement],i]==results or [i,Hashmap[complement]]==results) or results ==[]) :
                # 首先判断results是否是空集，是则添加[i,Hashmap[complement]]
                # 之后的判断中，把两个加数看成一对，判断是否是results的子集或者全集(注意元素顺序对查询的影响)，
                # 如果不是子集或者全集，results也不是空集，那么添加results
                    results.append(i)
                    results.append(Hashmap[complement])
        return results

if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    target = 9
    answer=Solution()
    results=answer.twoSum(nums, target)
    print(results)

Runtime: 40 ms, faster than 65.08% of Python online submissions for Two Sum.

Memory Usage: 13.4 MB, less than 5.02% of Python online submissions for Two Sum.

---

Approach 3: One-pass Hash Table

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.

Of cause, in this question, we assume that only one solution exists.

class Solution(object):
    def twoSum(self, nums, target):
        results = dict()
        for i in range(0, len(nums)):  # 一边将列表中的数添加到字典中，一边判断两数之差是否存在于字典中
            temp = target - nums[i]
            if temp in results:  # 判断步骤
                return [results[temp], i]
            results[nums[i]] = i  # 添加步骤（切记先判断再添加，以免key冲突）
        return "No Solution"

if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    target = 9
    answer=Solution()
    results=answer.twoSum(nums, target)
    print(results)