#include <iostream>
#include <vector>
#include <unordered_map>
#include <stdexcept>
/*
Two Sum — Return ALL Valid Pairs
--------------------------------
Goal:
Given a list of integers and a target value, return *all* index pairs
(i, j) such that nums[i] + nums[j] == target.
Algorithm:
- Use a hash map (unordered_map) mapping value → list of indices.
- As we iterate, compute complement = target - nums[i].
- If complement exists, append all pairs (stored_index, i).
- Then store nums[i] in the map for future matches.
Why this approach:
- Preserves original indices.
- Efficient: single pass, O(n) average-case.
- Handles duplicates naturally.
- Returns all valid pairs, not just one.
Complexity:
- Time: O(n) average-case; worst-case O(n^2) if many duplicates.
- Space: O(n) for the hash map.
Pitfalls:
- Many duplicates can produce many pairs; ensure vector capacity grows efficiently.
- No solution: return empty vector instead of throwing.
- Large inputs: avoid unnecessary copying.
Security Notes:
- No raw pointers; no manual memory management.
- No undefined behavior; bounds checked.
- Exceptions used only for critical errors.
Architecture Notes:
- Core logic isolated in a function (twoSumAllPairs).
- Main demonstrates multiple test scenarios.
- Clear separation of concerns: computation vs. I/O.
Test Edge Cases:
- Empty vector
- Single element
- No valid pair
- Multiple valid pairs
- Negative numbers
- Repeated numbers
- Large values
*/
std::vector<std::pair<int,int>> twoSumAllPairs(const std::vector<int>& nums, int target) {
// Map: value → list of indices where it appears
std::unordered_map<int, std::vector<int>> seen;
std::vector<std::pair<int,int>> result;
result.reserve(nums.size()); // performance hint
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
int complement = target - nums[i];
// If complement exists, add all pairs
if (seen.count(complement)) {
for (int idx : seen[complement]) {
result.emplace_back(idx, i);
}
}
// Store current index for future matches
seen[nums[i]].push_back(i);
}
return result; // empty if no pairs found
}
void printPairs(const std::vector<std::pair<int,int>>& pairs, const std::vector<int>& nums) {
if (pairs.empty()) {
std::cout << "No valid pairs found.\n";
return;
}
for (const auto& p : pairs) {
std::cout << "(" << p.first << ", " << p.second << ")"
<< " -> values (" << nums[p.first] << ", " << nums[p.second] << ")\n";
}
}
int main() {
// Test 1: Basic example
{
std::vector<int> nums = {2, 7, 11, 15};
int target = 9;
std::cout << "Test 1:\n";
auto pairs = twoSumAllPairs(nums, target);
printPairs(pairs, nums);
std::cout << "\n";
}
// Test 2: Multiple valid pairs
{
std::vector<int> nums = {1, 3, 2, 2, 3, 1};
int target = 4;
std::cout << "Test 2:\n";
auto pairs = twoSumAllPairs(nums, target);
printPairs(pairs, nums);
std::cout << "\n";
}
// Test 3: Negative numbers
{
std::vector<int> nums = {-1, -2, -3, -4, -5};
int target = -6;
std::cout << "Test 3:\n";
auto pairs = twoSumAllPairs(nums, target);
printPairs(pairs, nums);
std::cout << "\n";
}
// Test 4: No valid pairs
{
std::vector<int> nums = {10, 20, 30};
int target = 100;
std::cout << "Test 4:\n";
auto pairs = twoSumAllPairs(nums, target);
printPairs(pairs, nums);
std::cout << "\n";
}
// Test 5: Repeated values producing many pairs
{
std::vector<int> nums = {5, 5, 5, 5};
int target = 10;
std::cout << "Test 5:\n";
auto pairs = twoSumAllPairs(nums, target);
printPairs(pairs, nums);
std::cout << "\n";
}
}
/*
run:
Test 1:
(0, 1) -> values (2, 7)
Test 2:
(0, 1) -> values (1, 3)
(2, 3) -> values (2, 2)
(0, 4) -> values (1, 3)
(1, 5) -> values (3, 1)
(4, 5) -> values (3, 1)
Test 3:
(1, 3) -> values (-2, -4)
(0, 4) -> values (-1, -5)
Test 4:
No valid pairs found.
Test 5:
(0, 1) -> values (5, 5)
(0, 2) -> values (5, 5)
(1, 2) -> values (5, 5)
(0, 3) -> values (5, 5)
(1, 3) -> values (5, 5)
(2, 3) -> values (5, 5)
*/
