Leetcode Two Sum - Solution & Video Explaination

Solving using the Brute Force method

vector<int> TwoSum(vector<int>& nums, int target) {

  vector<int> target_indices;

  for (int i = 0; i < nums.size(); i++) {
    for(int j = i+1; j < nums.size(); j++) {

      if(nums.at(i) + nums.at(j) == target) {
        target_indices.push_back(i);
        target_indices.push_back(j);
        break;
      }

    }
  }

  return target_indices;
}

Solving using Hashmaps

vector<int> TwoSum(vector<int>& nums, int target) {
  vector<int> target_indices;

  unordered_map<int, int> hash_table;
  for (int i = 0; i < nums.size(); i++) {
    int second_integer = target - nums.at(i);

    if (hash_table.find(second_integer) != hash_table.end()) {
      target_indices.push_back(i);
      target_indices.push_back(hash_table.find(second_integer)->second);
      break;
    } else {
      hash_table[nums.at(i)] = i;
    }
  }

  return target_indices;
}

Complexity

Runtime: O(n)
Space: O(1)