Two Sum - C++ Solution

1. Introduction

The "Two Sum" problem is a classic algorithmic challenge that is often featured in coding interviews and assessments. It tests a developer's ability to understand array manipulation and efficient data structure usage, such as hash tables, in solving problems.

Problem

We are given an unsorted array of integers and a target sum. The objective is to find any pair of numbers in the array that adds up to the target sum. If such a pair exists, we return it; otherwise, we return (-1, -1) to indicate no valid pair was found. The problem can have multiple solutions, and any correct pair is an acceptable output.

2. Solution Steps

1. Use a hash map to store array values and their indices for quick lookups.

2. Traverse each element in the array.

3. For each element, calculate its complement by subtracting it from the target sum.

4. Check if this complement is already in the hash map. If yes, return the current element and its complement.

5. If not found, add the current element to the hash map.

6. If no pair is found, return (-1, -1).

3. Code Program

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

pair<int, int> findPair(vector<int>& nums, int target) {
    unordered_map<int, int> map; // Hash map to store elements and their indices
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i]; // Calculate complement
        if (map.find(complement) != map.end()) {
            return make_pair(nums[i], complement); // Return pair if complement is found
        }
        map[nums[i]] = i; // Add current element to map
    }
    return make_pair(-1, -1); // Return (-1, -1) if no pair is found
}

int main() {
    vector<int> nums = {8, 7, 2, 5, 3, 1};
    int target = 10;
    pair<int, int> result = findPair(nums, target);
    if (result.first != -1) {
        cout << "Pair found: (" << result.first << ", " << result.second << ")" << endl;
    } else {
        cout << "No valid pair found." << endl;
    }
    return 0;
}

Output:

Pair found: (8, 2) or Pair found: (7, 3)

Explanation:

The function findPair employs a hash map to efficiently search for the required pair. 

It iterates over the array elements, computing the complement (target - current element) for each. If this complement is found in the map, we return the pair, confirming the sum can be made. If not, the element is added to the map. 

The approach ensures a linear time complexity (O(n)), ideal for large arrays.