11. 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.

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

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

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

Problem Breakdown:

1. We create a hash map to store each number and its index as we iterate. This allows O(1) lookup for the complement.

• seen = {}

2. For each number, we calculate the complement needed to reach the target: complement = target - current number.

• for i, num in enumerate(nums):
      complement = target - num

3. We check if the complement exists in our hash map. If it does, we found our pair and return both indices.

• if complement in seen:
      return [seen[complement], i]

4. If the complement is not found, we store the current number and its index in the hash map for future lookups.

• seen[num] = i

Summary:

Use a hash map to store previously seen numbers and their indices. For each number, compute its complement (target - num) and check if the complement exists in the map. This converts a brute-force O(n^2) approach into a single-pass O(n) solution.

Time and Space Complexity:

Time Complexity: O(n) - we traverse the array once, and hash map lookups are O(1).

Space Complexity: O(n) - we store at most n elements in the hash map.

Python Solution:

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

JavaScript Solution:

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

Java Solution:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[] { seen.get(complement), i };
            }
            seen.put(nums[i], i);
        }
        return new int[] {};
    }
}