Two Sum - Java Solution

1. Introduction

This blog post covers a foundational problem in array manipulation and hashing known as the "Two Sum" problem. The objective is to find two numbers in an array that add up to a specific target value. This problem is a staple in algorithmic interviews and has applications in various areas including data analysis and financial computing.

Problem

Given an array of integers nums and an integer target, the task is to return the indices of the two numbers such that they add up to target. It is assumed that there is exactly one solution, and the same element cannot be used twice. The answer can be returned in any order.

2. Solution Steps

1. Use a hash map to store the complement of each element (target - element) and its index.

2. Iterate through the array:

a. For each element, check if it is present in the hash map.

b. If it is found, return the current index and the index stored in the hash map.

c. Otherwise, store the complement of the element (target - element) and its index in the hash map.

3. Since the problem guarantees a solution, the answer will be found during the iteration.

3. Code Program

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

public class TwoSum {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]"); // Test the function
    }

    // Function to find two numbers such that they add up to a specific 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);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Output:

[0, 1]

Explanation:

1. twoSum: This function identifies the indices of the two numbers in nums that add up to the target.

2. A hash map numMap is used to store the complement of each element (target - element) along with its index.

3. As the function iterates through nums, it checks if the current element is in numMap.

4. If it finds the element, it means a pair has been found that sums up to the target. The function then returns the indices of these two elements.

5. If the pair is not found, the function stores the complement of the current element and its index in numMap.

6. The use of a hash map allows for efficient look-up of complements, ensuring the solution is found quickly if it exists.

7. The approach guarantees finding the solution in a single pass through the array, making it an efficient solution for the problem.