LeetCode 1. Two Sum

bruteforce

Easiest way to solve this problem is bruteforcing. For each pair of integers, check whether their sum equals to target. If so, return their indexes.

  • Time Complexity = $ O(n^2) $
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for (int i=0; i<nums.size(); i++){
            for (int j=i+1; j<nums.size(); j++){
                if ((nums[i] + nums[j]) == target){
                    ans = {i, j};
                }
            }
        }
        return ans;
    }
};

hash

In order to reduce Runtime, implementing hash table will work. Searching in hash table is much faster than doing in array.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int, int> ref;
        for (int i=0; i<nums.size(); i++){
            ref[nums[i]] = i;
        }
        for (int i=0; i<nums.size(); i++){
            int pair = target - nums[i];
            if (ref.count(pair) != 0 && ref[pair] != i){
                ans = {i, ref[pair]};
                break;
            }
        }
        return ans;
    }
};