Two Sum easy

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.

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]

Steps

  1. Create a HashMap: We'll use a HashMap to store each number in nums as a key, and its index as the value.

  2. Iterate through the array: For each number num in nums:

    • Calculate the complement needed to reach the target ( complement = target - num).
    • Check if the complement exists as a key in the HashMap.
    • If it exists, we've found the pair! Return the index of the current number and the index of the complement (stored as the value in the HashMap).
    • If it doesn't exist, add the current number and its index to the HashMap.

  3. Handle cases where no solution is found: The problem statement guarantees a solution, so we don't need explicit error handling for this case.

Explanation

The HashMap provides efficient lookups (O(1) on average). Instead of checking every pair of numbers (which would be O(n^2)), we only need to iterate through the array once (O(n)). For each number, we check if its complement is already in the HashMap. This drastically reduces the time complexity.

Code

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>(); // Create a HashMap

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) { //Check if complement exists
                return new int[] { numMap.get(complement), i }; //Return indices
            }
            numMap.put(nums[i], i); //Add number and index to HashMap
        }

        //The problem statement guarantees a solution, so this line is unreachable
        return new int[] {}; 
    }
}

Complexity

  • Time Complexity: O(n), where n is the length of the input array nums. We iterate through the array once. HashMap lookups are O(1) on average.

  • Space Complexity: O(n) in the worst case, as the HashMap could store all the elements of nums if no pair is found early. In practice, it will often use less space.