Two Number Sum Problem - Java Solution

1. Introduction

This blog post addresses the Two Number Sum problem, a classic challenge in array manipulation and search algorithms. The objective is to find two numbers in an array that add up to a given target sum.

Problem

Given an array of integers, return the indices of the two numbers whose sum equals a given target. It is assumed that each input has exactly one solution, and the same element cannot be used twice.

Example:

Given nums = [2, 7, 11, 15], target = 9.

The output should be [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

2. Solution Steps

1. Create a HashMap to store the difference between the target and each element as keys, and their indices as values.

2. Iterate through the array.

3. For each element, check if it is present in the HashMap. If it is, we have found a pair that sums up the target.

4. If the pair is found, return the current index and the index from the HashMap.

5. If the pair is not found, add the difference and the current index to the HashMap.

6. Continue this process until the end of the array.

3. Code Program

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

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
    }

    // Method to find two numbers that add up to the target
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (numMap.containsKey(nums[i])) {
                return new int[] {numMap.get(nums[i]), i};
            }

            numMap.put(complement, i); // Store the complement and current index
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Output:

Indices: [0, 1]

Explanation:

In the array [2, 7, 11, 15], we are looking for two numbers that add up to 9. 

The twoSum method iterates through the array, storing the difference between the target and each element in a HashMap. 

When it finds an element in the HashMap that matches the current array element, it means a pair has been found. In this case, the numbers 2 and 7 (at indices 0 and 1) add up to 9, hence the output is [0, 1].