Tuesday, 11 July 2017

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. 

  3. 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
Share:

0 comments:

Post a Comment

Contact Me

Name

Email *

Message *

Popular Posts

Blog Archive