Leetcode -- Two Sum

information

• link：Two Sum - LeetCode
• Description：Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

solution

method 1

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

The function of the outside loop is to traverse nums.

At the fourth line, it judges whether v’s complement is in nums. If it is true, it will go in the second loop to find the index of v’s complement.

i+1 can avoid getting the same number.

the same idea but a little different ( by myself )

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, v in  enumerate(nums):
            if (target-v) in nums and nums.index(target-v) != i:
                return [i, nums.index(target-v)]

the same idea but a little different ( by the official solution )

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

However, all above are O(n^2).

method 2

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            hashmap[nums[i]] = i
        for i in range(len(nums)):
            if target-nums[i] in hashmap and hashmap[target-nums[i]] != i:
                return [i, hashmap[target-nums[i]]]

In python, dictionary is hashtable. Therefor, it can improve O(n) to almost O(1) when we search it.

method 3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            if target-nums[i] in hashmap:
                return [hashmap[target-nums[i]], i]
            hashmap[nums[i]] = i

This concept is that it tries check elements while inserting them into the hashtable.

In this way, we need to search forward. The clever part is that the previous elements is stored in the hashtable (hashmap)，so what we need to do is check if the complement is in hashtable and what is its index. And since the current number hasn’t been inserted yet, it avoids retrieving the same number.