Two Sum

Problem

https://leetcode.com/problems/two-sum/

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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 2 <= nums.length <= 10:sup:`4`

• -10:sup:`9`<= nums[i] <= 10:sup:`9`

• -10:sup:`9`<= target <= 10:sup:`9`

• Only one valid answer exists.

Follow-up:Can you come up with an algorithm that is less than O(n:sup:`2`) time complexity?

Pattern

Array, Hash Table

Approaches

Two Pointer

Explanation

Pair each value with its original index, then sort by value. Set two pointers i and j to the beginning and end of the sorted list. If nums[i] + nums[j] is less than target, increase the sum by moving i right; if greater, decrease the sum by moving j left. Stop when the sum equals target and return the two original indices.

Code

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    """Find two numbers in ``nums`` that add up to ``target``.
    """
    nums = list(enumerate(nums))  # keep track of the orignal indices
    nums = sorted(nums, key=lambda x: x[1])
    i = 0
    j = len(nums) - 1
    while i < j:
        twosum = nums[i][1] + nums[j][1]
        if twosum == target:
            break
        if twosum < target:
            i = i + 1
        if twosum > target:
            j = j - 1
    return [nums[i][0], nums[j][0]]

Test

>>> from two_sum__two_pointer import twoSum
>>> twoSum([2,7,11,15], 9)
[0, 1]
>>> twoSum([3,2,4], 6)
[1, 2]
>>> twoSum([3, 3], 6)
[0, 1]

Complexity

\(n\) is the length of the input array.

Time: \(O(n \log n)\) — dominated by the sort.

Auxiliary Space: \(O(n)\) — the enumerated-and-sorted copy.

two_sum__two_pointer.twoSum(nums: List[int], target: int) → List[int]

Find two numbers in nums that add up to target.

Hash Map

Explanation

Single pass: for each nums[i], check whether target - nums[i] is already present in a dict mapping previously-seen values to their indices. If so, the two indices form the answer; otherwise record nums[i] for later lookups.

Code

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    """Find two numbers in ``nums`` that add up to ``target``.
    """
    seen: dict[int, int] = {}
    for i, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], i]
        seen[value] = i
    return []

Test

>>> from two_sum__hash_map import twoSum
>>> twoSum([2, 7, 11, 15], 9)
[0, 1]
>>> twoSum([3, 2, 4], 6)
[1, 2]
>>> twoSum([3, 3], 6)
[0, 1]

Complexity

\(n\) is the length of the input array.

Time: \(O(n)\) — one pass with \(O(1)\) average-case dict lookups.

Auxiliary Space: \(O(n)\) — the dict stores at most \(n\) entries.

two_sum__hash_map.twoSum(nums: List[int], target: int) → List[int]

Find two numbers in nums that add up to target.