algorithm notes: leetcode#1 two sum

Problem

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

Basic idea

Use a hash table to map value to indice. We can iterate values of array, put each value and its indice into the hash table, and check whether the complement exists in the hash table. If the complement in the hash table, return two indices.

Python implementation

1
2
3
4
5
6
7
8
9
10
11
12

class (object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lookup = {}
        for idx, num in enumerate(nums):
            if target - num in lookup:
                return [lookup[target-num], idx]
            lookup[num] = idx

Time complexity analysis

Traverse the array only once, O(n).

Space complexity analysis

Use hash table to store value and indices. For a list containing n values, the hash table will store at most n elements, O(n).

Link

1. Two Sum
1. 两数之和
(中文版) 算法笔记: 力扣#1 两数之和