Two Sum

You are 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.

Approach: Hash Map (Optimal Solution)

Algorithm

1. Create a hash map to store values and their indices
2. Iterate through the array
3. For each element, calculate the complement (target - current value)
4. If complement exists in hash map, return the indices
5. Otherwise, store current value and index in hash map

Time & Space Complexity

• Time Complexity: O(n) - single pass through array
• Space Complexity: O(n) - hash map storage

Java Implementation

java

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

public class TwoSum {
    
    /**
     * Find indices of two numbers that add up to target.
     * @param nums Array of integers
     * @param target Target sum
     * @return Array containing indices of two numbers that sum to target
     */
    public static int[] twoSum(int[] nums, int target) {
        // Hash map to store value -> index mapping
        Map<Integer, Integer> numMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // If complement exists in map, we found our answer
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            
            // Store current number and its index
            numMap.put(nums[i], i);
        }
        
        // This should never be reached given problem constraints
        return new int[]{};
    }
    
    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        int[] result1 = twoSum(nums1, target1);
        System.out.println("Input: nums = [2, 7, 11, 15], target = 9");
        System.out.println("Output: [" + result1[0] + ", " + result1[1] + "]"); // Expected: [0, 1]
        
        // Test case 2
        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        int[] result2 = twoSum(nums2, target2);
        System.out.println("Input: nums = [3, 2, 4], target = 6");
        System.out.println("Output: [" + result2[0] + ", " + result2[1] + "]"); // Expected: [1, 2]
        
        // Test case 3
        int[] nums3 = {3, 3};
        int target3 = 6;
        int[] result3 = twoSum(nums3, target3);
        System.out.println("Input: nums = [3, 3], target = 6");
        System.out.println("Output: [" + result3[0] + ", " + result3[1] + "]"); // Expected: [0, 1]
    }
}

Alternative Implementation with Enhanced Output

java

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

public class TwoSumEnhanced {
    
    /**
     * Find indices of two numbers that add up to target.
     * @param nums Array of integers
     * @param target Target sum
     * @return Array containing indices of two numbers that sum to target
     */
    public static int[] twoSum(int[] nums, int target) {
        // Hash map to store value -> index mapping
        Map<Integer, Integer> numMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // If complement exists in map, we found our answer
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            
            // Store current number and its index
            numMap.put(nums[i], i);
        }
        
        // Return empty array if no solution found (shouldn't happen per problem constraints)
        return new int[]{};
    }
    
    /**
     * Helper method to print array
     */
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
    
    // Test method
    public static void main(String[] args) {
        System.out.println("Two Sum Problem - Java Implementation");
        System.out.println("=====================================");
        
        // Test case 1
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        int[] result1 = twoSum(nums1, target1);
        System.out.println("Test Case 1:");
        System.out.print("Input: nums = ");
        printArray(nums1);
        System.out.println("Target: " + target1);
        System.out.print("Output: ");
        printArray(result1);
        System.out.println();
        
        // Test case 2
        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        int[] result2 = twoSum(nums2, target2);
        System.out.println("Test Case 2:");
        System.out.print("Input: nums = ");
        printArray(nums2);
        System.out.println("Target: " + target2);
        System.out.print("Output: ");
        printArray(result2);
        System.out.println();
        
        // Test case 3
        int[] nums3 = {3, 3};
        int target3 = 6;
        int[] result3 = twoSum(nums3, target3);
        System.out.println("Test Case 3:");
        System.out.print("Input: nums = ");
        printArray(nums3);
        System.out.println("Target: " + target3);
        System.out.print("Output: ");
        printArray(result3);
    }
}

Example Walkthrough

For nums = [2, 7, 11, 15] and target = 9:

1. i=0, num=2: complement = 9-2 = 7. 7 not in map. Store {2: 0}
2. i=1, num=7: complement = 9-7 = 2. 2 is in map at index 0. Return [0, 1]

Key Points

1. HashMap Usage: Uses HashMap<Integer, Integer> to store value-index pairs
2. Single Pass: Only iterates through array once for O(n) time complexity
3. Index Retrieval: Returns the actual indices, not the values
4. Edge Cases: Properly handles duplicate values like [3,3] with target 6
5. Memory Efficiency: Uses O(n) space for the hash map

The Java implementation follows the same logic as the Python version but uses Java’s HashMap and array syntax. The solution is optimal with linear time and space complexity.