Two Sum

1. Two Sum

Easy

Find two numbers in an array that add up to a specific target.

ArrayHash Table

View Problem

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.

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]

Try It Yourself

TypeScript

function twoSum(nums: number[], target: number): number[] {
    // Your solution here
}

Go

func twoSum(nums []int, target int) []int {
    // Your solution here
}

Solution

Click to reveal solution

Use a hash map to store numbers we've seen and their indices for optimal O(n) time complexity.

TypeScript Solution

function twoSum(nums: number[], target: number): number[] {
  const hashmap = {};

  for (let i = 0; i < nums.length; i++) {
      if (nums[i] in hashmap) {
          return [hashmap[nums[i]], i];
      }

      hashmap[target - nums[i]] = i;
  }
}

Time:O(n)

Space:O(n)

Go Solution

func twoSum(nums []int, target int) []int {
  hashmap := map[int]int{}

  for i, num := range nums {
      index, ok := hashmap[num]
      if ok {
          return []int{index, i}
      }

      hashmap[target - num] = i
  }

  return []int{-1, -1}
}

Time:O(n)

Space:O(n)

Algorithm:

1. Create a hash map to store complements and their indices
2. Iterate through the array once
3. For each number, check if it exists in the hash map
4. If found, return the stored index and current index
5. If not found, store the complement (target - current number) with its index