Two Sum
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.
Constraints:
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
Input Format:
- An array of integers nums
- An integer target
Output Format:
- Return the indices of the two numbers that add up to the target.
Examples:
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]
Explanation:
Because nums[1] + nums[2] == 6, we return [1, 2].
Example 3:
Input:
nums = [3,3], target = 6
Output:
[0,1]
Explanation:
Because nums[0] + nums[1] == 6, we return [0, 1].
Solutions
Hash Table Approach
Use a hash table to store previously seen numbers and their indices. For each number, check if its complement exists in the hash table.
Brute Force Approach
Check all possible pairs of numbers using nested loops.
Algorithm Walkthrough
Example input: nums = [2,7,11,15], target = 9
Step-by-step execution:
- Initialize an empty hash map
- i=0: nums[0]=2, complement=9-2=7, 7 is not in the map, add {2:0} to map
- i=1: nums[1]=7, complement=9-7=2, 2 is in the map with value 0
- Return [0, 1]
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the array and how the hash table is built step by step to find the solution.
Key visualization elements:
- current element
- complement
- hash table state
Implementation Notes
This is one of the most common interview questions and a great introduction to using hash tables for optimal time complexity.