Two Sum

The Two Sum problem remains a classic and frequently asked question in many job interviews. It involves finding two numbers in an array that add up to a specific target.

Example

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

There can be certain, way we can solve this problem.

Naive approach 

We can loop to each number and loop through array to find the particular target

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

• Time Complexity: O(n²)
• Space Complexity: O(1)

Better approach 

Now as we know if x+y == target then x = target - y 

By this approach we can use the hash map and we will find the solution 

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.count(complement)) {
                return {numMap[complement], i};
            }
            numMap[nums[i]] = i;
        }
        return {}; 
    }
};

• Time Complexity: O(n)
• Space Complexity: O(n)