Question

How to implement the two sum algorithm to find two values in vector that add up to target with C++

Answer 1

#include <iostream>
#include <vector>
#include <map>

std::vector<int> twoSum(std::vector<int>& vec, int target) {
    std::map<int,int> mp;
    std::vector<int> vec_result;
    int size = vec.size();
    
    for (int i = 0; i < size; i++) {
        int diff = target - vec[i];
        if (mp.find(diff) != mp.end()) {
            auto result = mp.find(diff);        
            vec_result.push_back(result->second);
            vec_result.push_back(i);
            return vec_result;
        }
        mp.insert(std::make_pair(vec[i], i));
    }
          
    return vec_result;
}

int main() {
    std::vector<int> vec = {1, 5, 7, 6, 4, 3, 2}; 
    std::vector<int> result = twoSum(vec, 9);
    
    for (int i: result) {
        std::cout << i << " ";
    }
}


 
 
 
 
 
/*
run:
 
1 4 
 
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stdexcept>

/*
    Classic Two Sum
    ----------------
    Goal:
        Given a list of integers and a target value, return the indices of
        the two numbers that add up to the target.

    Approach:
        Use a hash map (unordered_map) to store previously seen values and
        their indices. For each element, compute the complement:
            complement = target - nums[i]
        If the complement exists in the map, we found the solution.

    Why this algorithm:
        - Single pass over the array.
        - Hash lookup is O(1) average-case.
        - No sorting required; original indices preserved.
        - Memory usage is proportional to the number of elements processed.

    Time Complexity:
        - O(n) average-case due to hash lookups.
    Space Complexity:
        - O(n) for the hash map.

    Pitfalls:
        - Duplicate values: handled naturally because map stores indices.
        - No solution: throw an exception or return an empty vector.
        - Large inputs: ensure efficient hashing and avoid unnecessary copies.

    Security Notes:
        - No raw pointers; no manual memory management.
        - No undefined behavior; bounds checked.
        - Exceptions used for error signaling.

    Architecture Notes:
        - Logic isolated in a function (twoSum).
        - Main function demonstrates usage and test cases.
        - Clear separation of concerns: computation vs. I/O.

    Test Edge Cases:
        - Empty vector
        - Single element
        - No valid pair
        - Multiple valid pairs (first encountered returned)
        - Negative numbers
        - Large numbers
*/

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    // Hash map: value → index
    std::unordered_map<int, int> seen;

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int complement = target - nums[i];

        // Check if complement already seen
        if (seen.count(complement)) {
            return { seen[complement], i };
        }

        // Store current value and index
        seen[nums[i]] = i;
    }

    // If no solution found, signal error
    throw std::runtime_error("No valid two-sum pair found.");
}

int main() {
    try {
        // Example input
        std::vector<int> nums = {2, 7, 11, 15};
        int target = 9;

        // Compute result
        auto result = twoSum(nums, target);

        // Output result
        std::cout << "Indices: " << result[0] << ", " << result[1] << "\n";
        std::cout << "Values: " << nums[result[0]] << ", " << nums[result[1]] << "\n";

        /*
            Additional Tests (manually verify or extend):
            ------------------------------------------------
            1. nums = {}, target = 10 → error
            2. nums = {5}, target = 5 → error
            3. nums = {3, 3}, target = 6 → returns {0, 1}
            4. nums = {-1, -2, -3, -4}, target = -6 → returns {1, 3}
            5. nums = {1, 2, 3, 4, 4}, target = 8 → returns {3, 4}
        */

    } catch (const std::exception& ex) {
        std::cerr << "Error: " << ex.what() << "\n";
    }
}



/*
run:

Indices: 0, 1
Values: 2, 7

*/

 

70+ SQL courses for beginners and professionals