Two Sum Problem and Solution

1. Introduction

The "Two Sum" problem is a classic algorithmic challenge that involves finding two numbers in an array that add up to a specific target number. Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target.

2. Solution in C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> indices;
    for (int i = 0; i < nums.size(); i++) {
        if (indices.find(target - nums[i]) != indices.end()) {
            return {indices[target - nums[i]], i};
        }
        indices[nums[i]] = i;
    }
    return {};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    for (int index : result) {
        cout << index << " ";
    }
    return 0;
}

Output:

0 1

Explanation:

1. A hash map (unordered_map) is used for storing the indices of the numbers.

2. Iterate through each number in the array.

3. Check if the complement (target - current number) exists in the map.

4. If it exists, return the pair of indices.

5. Otherwise, store the current number and its index in the map.

3. Solution in Java

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

public class TwoSum {
    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(complement)) {
                return new int[] { numMap.get(complement), i };
            }
            numMap.put(nums[i], i);
        }
        return new int[] {};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        for (int index : result) {
            System.out.print(index + " ");
        }
    }
}

Output:

0 1

Explanation:

1. A hash map (HashMap) is used for storing the indices of the numbers.

2. Iterate through each element in the array.

3. Check if the complement (target - current element) exists in the map.

4. If it exists, return the pair of indices.

5. Store the current element and its index in the map if not already present.

4. Solution in Python

def two_sum(nums, target):
    indices = {}
    for i, num in enumerate(nums):
        if target - num in indices:
            return [indices[target - num], i]
        indices[num] = i
    return []

nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)

Output:

[0, 1]

Explanation:

1. A dictionary (indices) is used for storing the indices of the elements.

2. Iterate through each element in the list.

3. Check if the complement (target - current element) exists in the dictionary.

4. If it exists, return the list of indices.

5. Otherwise, store the current element and its index in the dictionary.