LeetCode #1 Two Sum

Posted on | Post modified | In , , , , , , , , , ,

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

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Methods: Brute Force, Hash Table

Solution 1

Method: Brute Force

Time Complexity: O(n^2)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)

        for num_idx in range(length):
            for complement_idx in range(num_idx + 1, length):
                if nums[num_idx] + nums[complement_idx] == target:
                    return [num_idx, complement_idx]

        return None

back to method

Solution 2

Method: Hash Table

Time complexity: O(n)

Space complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        table = dict()

        for idx, key in enumerate(nums):
            if key not in table:
                table[key] = idx

            complement = target - key

            if complement in table.keys() and table[complement] != idx:
                return [table[complement], idx]

        return None

back to method