Question : You are given an array of integers and an integer SUM.Your task is to deteremine whether or not there exist two elements in array whose sum is exactly equal to given integer SUM and return the indexes if it exist.You may not use the same integer twice.

Input: arr[] = {0, -1, 2, -3, 1} sum = -2 Output: -3, 1

Brute Solution :

We can keep a pointer at the starting position of the array .Say pointer i is at arr[0] .Now arr[0]=0 .So we will be checking from i+1 to n-1 (n=size of array) , if sum-arr[0] exists , i.e. (-2-0)=-2 is there in the right part . becuse if we find -2 in i+1 to n-1 ; it will be (0+(-2))=sum where sum given is -2 . So it is basically ,
a+x=sum ; where sum is given and a is known to you . so to find x you will be doing ; x=sum-a , so you are going to find x in the right part of your array.

Now once you iterate from j=i+1 i.e. 0+1=1 to j=n-1 ; if we find the required integer just break the loop . but if you dont find the required integer just increase your i .i.e. do i++ and now iterate from j=i+1 i.e. (1+1)=2 to n-1.And repeat the process till you find the answer . But keep in mind ; run your i from 0 to n-2 so that you can have (n-1)th element as your j and you can add them up.
If you dont find the answer by running i=0 to n-2 ; then there doesnot exist any pair which sum up to given integer.
pseduo code :
for(i=0 to n-2){
for(j=i+1 to n-1){
if(arr[i]+arr[j]==sum){
you hit your answer
break; }
}
}

Time complexity=O(n^2)
Space complexity=O(1)

Optimal Solution :

For optimized time complexity solution ,we are going to use a extra space . We can use map for that .Take a empty map and start iterating given array , and check if (sum – arr[i]) exist in the map . and if it exist you have hit your answer ; but if it doesnot exist , add your current element i.e. arr[i] to the map .
Example :
arr[] = {0, -1, 2, -3, 1}

you have a empty map now (map->m) . start iterating.
Now , iterations :
i) -2-0=-2 ; it doesnot exist in the map . so just store it in the map ; m[0]=0;

ii) -2-(-1)= -1 ; it also not in the map as we have only 0 in map , so store it again ; now map looks like ; m={ 0,-1}

Similarly , when you reach -3 you will find that -1 already exist in the map , hence you got your answer .

Code :
C++
function to check the pair :

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

    map<int,int>m;
    vector<int>ans;
    for(int i=0;i<nums.size();i++)
    {
        if(m.find(target-nums[i])!=m.end())
        {
            ans.push_back(m[target-nums[i]]);
            ans.push_back(i);
            return ans;
        }
        m[nums[i]]=i;

    }
    return ans;

}