The Two Sum problem is a common algorithmic challenge that requires finding two numbers in an array that add up to a specific target value. This solution uses a hash map for efficient lookups.

Program Explanation

The following Java program uses a HashMap to store the numbers and their corresponding indices. This allows for an average time complexity of O(n) for finding the two numbers that sum to the target.

Java Code

import java.util.HashMap;

public class TwoSum {
    /**
     * Finds two indices of the numbers in the array that add up to the target value.
     *
     * @param nums   the array of integers
     * @param target the target sum
     * @return an array containing the indices of the two numbers, or an empty array if no solution exists
     */
    public int[] twoSum(int[] nums, int target) {
        // Create a hash map to store the value and its index
        HashMap<Integer, Integer> numMap = new HashMap<>();

        // Iterate through the array
        for (int i = 0; i < nums.length; i++) { // Calculate the complement int complement = target - nums[i]; // Check if the complement exists in the map if (numMap.containsKey(complement)) { // Return the indices of the complement and the current number return new int[] { numMap.get(complement), i }; } // Store the number and its index in the map numMap.put(nums[i], i); } // Return an empty array if no solution is found return new int[0]; } // Example usage public static void main(String[] args) { TwoSum twoSum = new TwoSum(); int[] nums = {2, 7, 11, 15}; int target = 9; int[] result = twoSum.twoSum(nums, target); if (result.length > 0) {
            System.out.println("Indices of the two numbers: " + result[0] + " and " + result[1]);
        } else {
            System.out.println("No two numbers add up to the target.");
        }
    }
}

How It Works

• The program defines a method twoSum that takes an integer array and a target sum.
• A HashMap is used to keep track of the numbers and their indices.
• For each number in the array, it calculates the complement (the number that needs to be added to the current number to reach the target).
• If the complement is already in the map, the indices of the two numbers are returned.
• If no such pair is found by the end of the loop, an empty array is returned.

Complexity Analysis

• Time Complexity: O(n) – Each number is processed once.
• Space Complexity: O(n) – In the worst case, all numbers are stored in the hash map.