1. Two Sums

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Brute force solutions

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> v;
        int s=0;
        for(int i=0;i<nums.size();i++){
            
            for(int j=i+1;j<nums.size();j++){
                
                s=nums[i]+nums[j];
                if(s==target)
                {
                    v.push_back(i);
                    v.push_back(j);
                    break;
                }
            }
        }
        
        return v;
        
    }
};

Time Complexity O(n^2)

Optimized solution using Hash Map

1. This solution uses unordered_multimaps to handle the same values. Time Complexity O(n).

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {

        vector<int> v;
        unordered_multimap<int, int> m;

        for (int i = 0; i < nums.size(); i++)
        {
            m.insert({nums[i], i});
        }

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

            int tar = target - nums[i];
            if (tar != nums[i])
            {
                if (m.find(tar) != m.end())
                {
                    auto a = m.find(nums[i]);
                    auto b = m.find(tar);
                    v.push_back(a->second);
                    v.push_back(b->second);
                    break;
                }
            }

            else
            {
                if (m.count(tar) > 1)
                {
                    auto a = m.equal_range(tar);
                    for (auto it =a.first; it != a.second; it++) { 
                        v.push_back(it->second);
                    } 
                 break;
                }
                
            }
        }
       

        return v;
    }
};

2. This solution uses unordered_maps and vector. Time Complexity O(n).

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {

        vector<int> v;
        unordered_map<int, vector<int>> m;

        for (int i = 0; i < nums.size(); i++)
        {
            m[nums[i]].push_back(i);
        }

        for (int i = 0; i < nums.size(); i++)
        {
            int dif = target - nums[i];

            if (dif == nums[i])
            {
                vector<int> k = m[nums[i]];
                if (k.size() == 2)
                {
                    v.push_back(k[0]);
                    v.push_back(k[1]);
                    break;
                }
            }
            else if (m.find(dif) != m.end())
            {
                vector<int> k1 = m[nums[i]];
                vector<int> k2 = m[dif];
                v.push_back(k1[0]);
                v.push_back(k2[0]);
                break;
            }
        }

        return v;
    }
};

Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        int i = 0;
        vector<int> v;
        int start = 0;
        int end = nums.size() - 1;

        while (start < end)
        {
            if (((nums[start] + nums[end]) - target) > 0 )
            {
               end--; 
            }
            else if(((nums[start] + nums[end]) - target) < 0 )
            {
                start++;
                
            }
            else{
                v.push_back(start+1);
                v.push_back(end+1);
                break;
            }
        }
        return v;
    }
};

Using Two Poiner method: Time Complexity O(n) , Space Complexity: O(1)