◻️1. Two Sum (easy)

[NOT a 2 pointer problem as array is not sorted.]

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]
Explanation: 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]

---

Solutions

Brute Force

Runtime 52 ms Memory 12.76 MB

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

Optimised

Runtime 4 ms Memory 13.76 MB

// Done on my own by referring to Striver YT and GFG.
// Algo: (use map data-structure.)
// 1. First find if (target-nums[i]) is there on map or not.
// 2. If there, then return index values.
// 3. Else store (target-nums[i]).

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mpp;
        for(int i=0; i<nums.size(); i++){
            if(mpp.find(target - nums[i])!=mpp.end())
                return std::vector<int>{ mpp.find(target - nums[i])->second, i };
            else
                mpp.insert({nums[i], i});
                // mpp[nums[i]] = i;
        }
        return std::vector<int>{};
    }
};