Two Sum - LeetCode Solution in C++

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 an 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.