approach 1

hash table

Using brute force, time complexity is O(n²). And we know that at least we need to loop through nums once to get all the information. So we can try a more efficient way to check if the complement exist. For a number a, we check if the number (target - a) exist, if do, we output the two indexes. By using the hash table, can reduce the checking time form O(n) to O(1).

C++ code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) hash[nums[i]] = i;

        for (int i = 0; i < nums.size(); i++) {
            int need = target - nums[i];
            if (hash.count(need) && hash[need] != i) return {hash[need], i};
        }
        return {};
    }
};

approach 2

one-pass hash table

before we insert number to the hash table, we can check if the number we need is already in the table.

C++ code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            int need = target - nums[i];
            if (hash.count(need)) return {hash[need], i};
            hash[nums[i]] = i;
        }
        return {};
    }
};