1. 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 <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

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

Solution

Concept

The task is to find two indices $i$ and $j$ in the array nums such that: $\text{nums}[i]+\text{nums}[j]=\text{target}$

We have the following constraints:

1. Each input will have exactly one solution.
2. Indices $i$ and $j$ must be distinct.
3. The solution must be efficient, ideally better than $O(n^2)$.

---

Naive Approach

1. Use two nested loops to check every pair of numbers in the array.
2. For each pair, check if their sum equals the target.
3. Return the indices if a match is found.

Time Complexity: $O(n^2)$ (inefficient for large arrays).

---

Optimized Approach: Using a Hash Map

The optimized solution uses a hash map (dictionary) to store the difference between the target and each element as we iterate through the array.

Steps:

1. Create an empty hash map to store values we’ve seen so far as key-value pairs.
2. Traverse the array. For each number, calculate its complement: $\text{complement}=\text{target}-\text{nums}[i]$
3. Check if the complement exists in the hash map:
   • If it does, return the current index and the index of the complement.
   • If it doesn’t, add the current number and its index to the hash map.
4. Continue until the solution is found (guaranteed as per constraints).

Time Complexity: $O(n)$, since we traverse the array once. Space Complexity: $O(n)$, for the hash map.

---

Implementation

Here are some implementations of the optimized solution:

def twoSum(nums, target):
    # Dictionary to store the value and its index
    num_map = {}
    
    # Iterate through the array
    for i, num in enumerate(nums):
        complement = target - num
        
        # Check if complement exists in the dictionary
        if complement in num_map:
            return [num_map[complement], i]
        
        # Add current number and its index to the dictionary
        num_map[num] = i

import java.util.HashMap;
 
public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] {numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
        }
        return new int[0]; // No solution, but the problem guarantees a solution exists
    }
}
 

#include <unordered_map>
#include <vector>
 
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> num_map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (num_map.find(complement) != num_map.end()) {
            return {num_map[complement], i};
        }
        num_map[nums[i]] = i;
    }
    return {};
}
 

using System;
using System.Collections.Generic;
 
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> numMap = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (numMap.ContainsKey(complement)) {
                return new int[] {numMap[complement], i};
            }
            numMap[nums[i]] = i;
        }
        return new int[0];
    }
}
 

function twoSum(nums, target) {
    const numMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        numMap.set(nums[i], i);
    }
}
 

function twoSum(nums: number[], target: number): number[] {
    const numMap: Map<number, number> = new Map();
 
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
 
        // Check if the complement exists in the map
        if (numMap.has(complement)) {
            return [numMap.get(complement)!, i];
        }
 
        // Add the current number and its index to the map
        numMap.set(nums[i], i);
    }
 
    // Problem guarantees a solution, so no need for a fallback return
    throw new Error("No solution found");
}
 

---

Example Walkthrough

Example 1

Input: nums = [2, 7, 11, 15], target = 9

1. Start with num_map = {}.
2. Iterate:
   • $i=0$, $\text{num}=2$, $\text{complement}=9-2=7$:
     • 7 is not in num_map.
     • Add 2 to the map: num_map = {2: 0}.
   • $i=1$, $\text{num}=7$, $\text{complement}=9-7=2$:
     • 2 is in num_map with index 0.
     • Return [0, 1].

Output: [0, 1]

---

Example 2

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

1. Start with num_map = {}.
2. Iterate:
   • $i=0$, $\text{num}=3$, $\text{complement}=6-3=3$:
     • 3 is not in num_map.
     • Add 3 to the map: num_map = {3: 0}.
   • $i=1$, $\text{num}=2$, $\text{complement}=6-2=4$:
     • 4 is not in num_map.
     • Add 2 to the map: num_map = {3: 0, 2: 1}.
   • $i=2$, $\text{num}=4$, $\text{complement}=6-4=2$:
     • 2 is in num_map with index 1.
     • Return [1, 2].

Output: [1, 2]