leetcode_two-sum

leetcode problem solving

https://leetcode.com/problems/two-sum/

Brute-force solution : O(n^2)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 1. O(n^2) solution
        // Brute-force : pick the two number;
        vector<int> answer = vector<int>();
        for (int i=0; i < nums.size(); i++){
           int pivot = nums[i];
           for (int j=i + 1; j < nums.size(); j++){
               int sum = pivot + nums[j];
               if(sum == target){
                   answer.push_back(i);
                   answer.push_back(j);
                   return answer;
               }
           }
        }
        return answer;
    }
}

Hash table using solution : O(n)

The key idea is the complement of an answer number must exist (an answer number + the complement number = target). So we just should minimize the time to find the complement number, which I found a hash table is the one. Search the complement number in the existing hash table, and if not found, add the number to the hash table.
DONE

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 2. O(n) solution
        // using hash table
        unordered_map<int, int> hash_table;
        vector<int> answer = vector<int>();
        for (int i=0; i < nums.size(); i++){
            int complement = target - nums[i];
            if (hash_table.find(complement) != hash_table.end()){
                answer.push_back(hash_table[complement]);
                answer.push_back(i);
                return answer;
            }
            hash_table[nums[i]] = i;
        }
        return answer;
    }
};