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

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 (dictionary) to store numbers we have already seen along with their indices. The key is the number and the value is its index. This allows O(1) lookup time.

• seen = {}

2. We loop through the array using enumerate to get both the index and value. For each number, we calculate what its complement would be (target - current number).

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

3. We check if the complement already exists in our hash map. If it does, we have found our pair - the current index and the index stored in the hash map for the complement.

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

4. If the complement is not in the hash map, we add the current number and its index to the hash map so future iterations can find it as a complement.

• seen[num] = i

Summary:

Use a hash map to store previously seen numbers and their indices. For each number, calculate its complement (target - number) and check if it exists in the hash map. This converts a brute force O(n^2) solution into an O(n) one-pass solution by trading space for time.

Time and Space Complexity:

Time Complexity: O(n) - we traverse the list containing n elements only once.

Space Complexity: O(n) - the extra space required depends on the number of items stored in the hash map, which stores at most n elements.

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<Integer, Integer> 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[] {};
    }
}