twoSum

Problem Statement

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.

Constraints:
1. 2 <= nums.length <= 104
2. -109 <= nums[i] <= 109
3. -109 <= target <= 109
4. Only one valid answer exists.

Examples:

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,3], target = 6
Output: [0,1]

Solutions

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 - xtarget−x.

class Solution(object):
    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 nums[i] + nums[j] == target:
                    return [i, j]

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.

class Solution(object):
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Create a hash table to store the numbers and their indices using dictionary comprehension
        hash_table = {nums[i]: i for i in range(len(nums))}   

        for i in range(len(nums)):
            # Calculate the complement of the current number
            complement = target - nums[i]
            # If the complement is in the hash table and it's not the current number itself
            if complement in hash_table and hash_table[complement] != i:
                # Return the indices of the two numbers that add up to the target
                return [i, hash_table[complement]]

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.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    # Create a hash table to store the numbers and their indices
    hash_table = {}
    for i in range(len(nums)):
        # Calculate the complement of the current number
        complement = target - nums[i]
        # If the complement is in the hash table
        if complement in hash_table:
            # Return the indices of the two numbers that add up to the target
            return [hash_table[complement], i]
        # Store each number and its index in the hash table
        hash_table[nums[i]] = i

References

LeetCode - twoSum