MENU

Two Sum

Two Sum

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

Java Approach

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];        
        for(int i = 0; i < nums.length; i++) {
            for(int n = i + 1; n < nums.length; n++) {
                if( nums[i] + nums[n] == target) {
                    res[0] = i;
                    res[1] = n;
                }
            }
        }
        return res;
    }    
}

Python Approach

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

Idea:Use two level for loop to check every element。Idea is simple but time complexity = O(n^2)

Improvement

Trying to use hash map to store the index and value in nums. Because known there's the only solution in every list, if find a result in seen map, I just return both index of the result, and i.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, v in enumerate(nums):
            remain = target - v
            if remain in seen:
                return [seen[remain], i]
            seen[v] = i
        return []
Last Modified: October 7, 2020