[LeetCode] Two Sum

Problem Statement (link):

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis:
The naive approach is to scan every pairs, which requires O(n^2) --> TLE.

Consider using map, which has O(log n) time complexity. For each number, we need to find if there's another number such that the two add up to the target number. The search is O(log n).

A corner case we need to consider is: e.g., if target==6, and there's only one 3 in vector<int> numbers, we need to eliminate the index of current position i (see code below).

The overall algorithm complexity is O(n logn). For a detail comparison of std::map and std::unordered_map, please see the Note below.

Code:

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> out;
        if (numbers.size()<2) return out;
            map<int, int> map;
            // Create map
            for (int i=0; i<numbers.size(); i++) {
                map[numbers[i]]=i;
            }
            // Find if the pair exists
            for (int i=0; i<numbers.size(); i++) {
                int diff=target-numbers[i];
                // found in hashmap && it's a differnt element
                if (map.find(diff)!=map.end() && map.find(diff)->second!=i) {
                    out.push_back(i+1);
                    out.push_back(map[diff]+1);
                    return out;
                }
            }
        return out;
    }
};

Note:

std::map vs. std::unordered_map

	std::map	std::unordered_map
Element ordering	ordered	Un-ordered
Implementation in C++11	Red-black tree (or balanced tree)	Hash table
Search time complexity	O(log(n))	O(1) if no hash collisions Up to O(n) if there are collisions
Insertion time complexity	O(log(n)) + re-balance	Same as search
Deletion time complexity	O(log(n)) + re-balance	Same as search
Need hash function	No	Yes
Space utilization	Use less memory (just pointers)	Use more memory
Common use cases	When good hash is not possible or too slow. Or when order is required	Other cases