Solving the Two Sum Problem in C++

To solve the “Two Sum” problem in C++, there are mainly two mainstream methods: brute force enumeration and hash table. Below, I will explain the implementation of these two methods in detail and provide code examples.

Here is a comparison table of the two solutions to help you quickly understand their characteristics:

| Method | Time Complexity | Space Complexity | Core Idea | Applicable Scenarios |

| :— | :— | :— | :— | :— |

| Brute Force Method | O(n²) | O(1) | Double loop to traverse all possible combinations | Small data size, high space complexity requirements |

| Hash Table Method | O(n) | O(n) | Use a hash table to store traversed values and their indices for quick lookup | Large data size, focus on time complexity |

💡 Method 1: Brute Force Method

This is the most straightforward solution. We use two nested loops to check each pair of different elements in the array to see if their sum equals the target value.

Code Implementation

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        // Outer loop, traversing from the first element to the second last element
        for (int i = 0; i < n - 1; ++i) {
            // Inner loop, starting from the element after i
            for (int j = i + 1; j < n; ++j) {
                // Check if the sum of the two numbers equals the target
                if (nums[i] + nums[j] == target) {
                    return {i, j}; // Return indices immediately upon finding
                }
            }
        }
        return {}; // According to the problem statement, a solution must exist; this return is to ensure function completeness
    }
};

Algorithm Analysis

– Time Complexity: O(n²). It requires traversing “n(n-1)/2” pairs of elements.

– Space Complexity: O(1). Only constant extra space is used.

🚀 Method 2: Hash Table Method (Recommended)

To optimize lookup speed, we can use a hash table (commonly using “std::unordered_map” in C++). The core idea is to trade space for time: while traversing the array, we record each element’s value and its index in the hash table. For each element “nums[i]”, we calculate its complement “complement = target – nums[i]” and then check if this complement already exists in the hash table. If it does, we have found the answer.

Code Implementation

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap; // Key: value of array element, Value: corresponding index
        
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            // Check if the complement is already in the hash table
            if (numMap.find(complement) != numMap.end()) {
                // Found the target, return the index of the complement and the current index
                return {numMap[complement], i};
            }
            // Store the current element's value and index in the hash table for future lookup
            numMap[nums[i]] = i;
        }
        return {}; // Ensure the function has a return value
    }
};

Algorithm Analysis

– Time Complexity: O(n). Only requires traversing the array once, with an average time complexity of O(1) for each lookup and insertion operation in the hash table.

– Space Complexity: O(n). The hash table may need to store up to n elements.

💎 Summary and Choice

– The brute force method has a simple idea, and the code is easy to write, which is acceptable for small input sizes.

– The hash table method is a more efficient general solution, significantly reducing time complexity by sacrificing some space, especially suitable for handling large-scale data.

In actual interviews or problem-solving scenarios, if there are requirements for time complexity, it is recommended to implement the hash table solution first.

I hope these detailed explanations and code examples help you thoroughly understand the “Two Sum” problem. If you have any further questions, feel free to ask!