Pair with given Sum (Two Sum)

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Example:

Input:

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

Output:

[0, 1]

Explanation: nums[0] + nums[1] = 2 + 7 = 9

Algorithm

You can solve this problem in various ways:

1. Brute Force

• Check every possible pair of numbers.
• Time Complexity: O(n^2)

2. Hash Map (Optimized Solution)

• Use a dictionary to store the difference between the target and the current number.
• Time Complexity: O(n)

Two Sum problem in various programming languages:

C

#include <stdio.h>

void twoSum(int nums[], int size, int target) {
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (nums[i] + nums[j] == target) {
                printf("[%d, %d]\n", i, j);
                return;
            }
        }
    }
    printf("No solution found\n");
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int size = sizeof(nums) / sizeof(nums[0]);

    twoSum(nums, size, target);
    return 0;
}

CPP

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

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

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    vector<int> result = twoSum(nums, target);
    if (!result.empty()) {
        cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    } else {
        cout << "No solution found" << endl;
    }
    return 0;
}

JAVA

import java.util.HashMap;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.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);
        if (result.length > 0) {
            System.out.println("[" + result[0] + ", " + result[1] + "]");
        } else {
            System.out.println("No solution found");
        }
    }
}

Python

pythonCopy codedef two_sum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

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

result = two_sum(nums, target)
if result:
    print(result)
else:
    print("No solution found")

---

C#

using System;
using System.Collections.Generic;

class TwoSum {
    public static int[] TwoSumSolution(int[] nums, int target) {
        Dictionary<int, int> map = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (map.ContainsKey(complement)) {
                return new int[] { map[complement], i };
            }
            map[nums[i]] = i;
        }
        return new int[] {};
    }

    static void Main(string[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] result = TwoSumSolution(nums, target);
        if (result.Length > 0) {
            Console.WriteLine($"[{result[0]}, {result[1]}]");
        } else {
            Console.WriteLine("No solution found");
        }
    }
}

---

JavaScript

function twoSum(nums, target) {
    const numMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        numMap.set(nums[i], i);
    }
    return [];
}

const nums = [2, 7, 11, 15];
const target = 9;

const result = twoSum(nums, target);
if (result.length > 0) {
    console.log(result);
} else {
    console.log("No solution found");
}