Find indices of Target sum in a given array in C++

In this tutorial, we will be solving a popular algorithmic challenge. This question can be found on leetcode as TwoSum. We will be solving this Two Sum problem in C++.

Two Sum Problem in C++

Our goal in this tutorial is given a target sum, we will have to return an array that has two integers. The integers should be such that they are indices in the earlier given array whose values add up to exactly a given sum.

There are two approaches to this problem. One is accessing all such pairs in the array. Such a search method will require us to compare every element with one another. This gives us nearly a time complexity of O(n^2). This is great since we can really find a solution but we can do much better.

We will be able to solve this problem in O(n) (linear time complexity) by making use of extra space. We will use a hash table that stores seen values till a point. We can check for every element we access in the array to see if (target – current element in the array) exists in the hash set.

Since we make use of the fact that the access time of an element in a has set is constant time, we can asymptomatically assume we solve this problem in Linear time.

Input:

4

10

4 6 11 16

Output:

0 1
#include <stdio.h>
#include <bits/stdc++.h>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> mymap;
        vector <int> result;
        for(int i=0; i<nums.size(); i++){
            if(mymap.find(target-nums[i])==mymap.end())
            mymap[nums[i]]=i;
            if(mymap.find(target-nums[i])!=mymap.end()){
                  if(mymap[target-nums[i]]!=i){
                    result.push_back(mymap[target-nums[i]]);
                    result.push_back(i);
                }
                
            }
        }
        return result;
    }
int main()
{
    int n;
    cin>>n;
    vector<int>array1;
    int target;
    cin>>target;
    for(int i=0; i<n; i++){
        int num;
        cin>>num;
        array1.push_back(num);
    }
    vector<int>result;
    result=twoSum(array1, target);
    for(auto g: result)
    cout<<g<<" ";
    

    return 0;
}

Also read:

Leave a Reply