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.

Examples:

• Input: nums = [2, 7, 11, 15], target = 9
  Output: [0, 1]
  Explanation: nums[0] + nums[1] = 2 + 7 = 9
• Input: nums = [3, 2, 4], target = 6
  Output: [1, 2]
  Explanation: 2 + 4 = 6
• Input: nums = [3, 3], target = 6
  Output: [0, 1]
  Explanation: 3 + 3 = 6

Solution 1: Brute Force Approach

Logic:

• Check every pair of numbers.
• If their sum is equal to the target, return their indices.

public class TwoSumBruteForce {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{}; // No solution found
    }
}

Drawback: Too slow for large arrays.

Approach 2: Optimized Approach using HashMap

• Start with an empty HashMap.
• Go through each number in the array one by one.
• For each number:
• Calculate the number you need to reach the target (target - current number). This is called the complement.
• Check if the complement already exists in the map:
  • If it does, we found the answer! Return the current index and the index of the complement from the map.
  • If it doesn’t, store the current number and its index in the map so it can be used later.

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

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(); // value -> index

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            // If complement already exists in the map, return both indices
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }

            // Otherwise, store the current number and its index
            map.put(nums[i], i);
        }

        // No solution found (won't happen as per problem constraints)
        return new int[]{};
    }
}

• HashMap makes it fast by storing what we’ve seen.
• You check if the required pair has already been seen.