1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,





Return [0, 1] since nums[0] + nums[1] = 2 + 7 = 9

Approach:

1. The brute force solution is to use two loops and find the two indices. The time complexity of this solution is O(n ^ 2)



#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        int n = nums.size();
        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++){
                if(nums[i] + nums[j] == target){
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
        return result;
    }
};



2. A time efficient solution would be to use hash maps and find the two numbers in O(n) time assuming hash maps take O(1) time. 



class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> indexMap;
        vector<int> result;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(indexMap.find(target - nums[i]) != indexMap.end()){
                result.push_back(indexMap[target - nums[i]]);
                result.push_back(i);
                return result;
            } else{
                indexMap[nums[i]] = i;
            }
        }
        return result;
    }
};

Here is the ideone link for the solution: 2 Sum : http://ideone.com/O74qFR

Read More