Two Sum Problem: Brute‑Force, Hash‑Table, and Sort‑with‑Binary‑Search Solutions in C++

Hello, I'm Xiao Feng. In this new series on Data Structures and Algorithms, we start with the classic LeetCode problem "Two Sum".

Problem Statement

Given an integer array nums and an integer target , find the indices of the two numbers such that they add up to target . Example: nums = [2,7,11,15], target = 9 → output [0,1] .

Brute‑Force Solution

The simplest method fixes each element and scans the rest of the array, resulting in O(n²) time complexity.

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                res.push_back(i);
                res.push_back(j);
            }
        }
    }
    return res;
}

Although this code can be accepted, it is inefficient.

Hash‑Table Solution

Since the problem is essentially a search for target - nums[i] , a hash table provides constant‑time look‑ups.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        auto iter = map.find(target - nums[i]);
        if (iter == map.end()) {
            map[nums[i]] = i;
        } else {
            res.push_back(i);
            res.push_back(iter->second);
        }
    }
    return res;
}

This algorithm runs in O(n) time because hash‑table operations are on average O(1).

Sort + Binary Search Solution

If library hash tables are unavailable, we can sort the array (keeping original indices) and then use binary search.

void quick_sort(vector<pair<int,int>>& nums, int b, int e) {
    if (b > e) return;
    int i = b - 1;
    for (int k = b; k < e; k++) {
        if (nums[k].second < nums[e].second) {
            swap(nums[++i], nums[k]);
        }
    }
    swap(nums[++i], nums[e]);
    quick_sort(nums, b, i - 1);
    quick_sort(nums, i + 1, e);
}

int binary_search(vector<pair<int,int>>& nums, int b, int e, int target) {
    while (b <= e) {
        int m = (b + e) / 2;
        if (nums[m].second == target) {
            return nums[m].first;
        } else if (nums[m].second < target) {
            b = m + 1;
        } else {
            e = m - 1;
        }
    }
    return -1;
}

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    vector<pair<int,int>> nums_index;
    int size = nums.size();
    for (int i = 0; i < size; i++) {
        nums_index.push_back(pair<int,int>(i, nums[i]));
    }
    quick_sort(nums_index, 0, size - 1);
    for (int i = 0; i < size - 1; i++) {
        int r = binary_search(nums_index, i + 1, size - 1, target - nums_index[i].second);
        if (r != -1) {
            res.push_back(nums_index[i].first);
            res.push_back(r);
        }
    }
    return res;
}

This approach has O(n log n) sorting time plus O(n log n) for the binary searches, making it slower than the hash‑table method, but it demonstrates how sorting and binary search can solve the problem.

Overall, the article shows that a single problem can be tackled with multiple algorithmic ideas—brute force, hash tables, and sort‑plus‑binary‑search—each with different trade‑offs in complexity and performance.