Two Sum: finding two numbers in an array that add up to a given target number

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.

- You are given an array of integers and a target sum.
- The task is to find two distinct numbers in the array that add up to the target.
- You should return their indices as a result.

Understanding the Problem

- Start by considering a brute force approach where you check every possible pair.
- For each number, iterate through the remaining numbers and check if they add up to the target.
- This approach has O(n²) time complexity.

Brute Force Approach (Inefficient)

- The core operation is checking whether two numbers in the array add up to the target.
- For each number `num`, check if there’s another number `complement` such that:
  `num + complement = target`
- The complement can be calculated as `complement = target - num`.

Identifying the Core Operation

- Searching through the array takes O(n) time if done linearly. To make this faster, you can use a hash map (dictionary).
- A hash map allows for constant-time lookups (O(1)), so you can check if the complement exists as you iterate through the array.

Using a Hash Map for Efficient Lookup

- Create an empty hash map to store numbers and their indices as you iterate through the array.

Initializing the Hash Map

- Loop through the array.
- For each number, calculate its complement (the difference between the target and the current number).
- The complement is calculated as `target - num`.

Iterate Through the Array and Calculate Complement

- For each number, check if the complement exists in the hash map.
- If the complement is already in the hash map, it means you’ve found two numbers that add up to the target.
- Return the indices of the current number and its complement.

Check if the Complement Exists in the Hash Map

- If the complement is not found in the hash map, store the current number and its index in the hash map.
- This ensures that it can be checked as a complement for future numbers.

Store the Current Number in the Hash Map

- Ensure that the input array has at least two numbers.
- Return `None` if no solution is found.

Interview question: Two Sum

Example 1

Example 2

Example 3

Test

Results