thesarfo

Reference

Two Sum

Finding whether (or where) two array elements sum to a target — nested loops vs. a single hashmap pass.

views 0

Two flavors: does a pair summing to target exist (return boolean), or find the pair’s indices. (LeetCode 1)

Brute force: compare every pair — O(n²), or halved by only comparing each pair once (j = i + 1 instead of j = 0).

Optimal — hashmap: for each element, compute target - element and check whether that complement has already been seen.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mpp; // element -> index


        for (int i = 0; i < nums.size(); i++) {
            int a = nums[i];
            int more = target - a;
            if (mpp.find(more) != mpp.end()) {
                return {mpp[more], i};
            }
            mpp[a] = i;
        }
        return {0, 0};
    }
};

Time: O(n).