Two Sum — LeetCode

Two Sum - LeetCode

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]

we may check every single possibility . We’ll start by iterating from 0th index to (n-1)th index. For every index we have to possible choices whether to include it or not.So if the array size in n then we might check every possibility and end up with 2^n combinations.

But in this question we just have to return two indexes if numbers which sum up to target.

Solution 1:

Let’s have a look into the question , we just have to return two indexes of numbers whose sum is target then we just have to check whether both the values exist or not.

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

Time complexity : O(n*n)
Space Complexity: O(1) [because constant space]

Using STL’s
let iterate over the vector from begin() to end() so for every element we check whether the complement of it exists in the array or not.

class Solution {
public:    
vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++){
         auto it=find(nums.begin(),nums.end(),target-nums[i]);
            if(it!=nums.end()){
                return {i,distance(nums.begin(),it)-1};
            }
        }
return nums;
    }
};

Time complexity : O(n*n)
Space Complexity: O(1)

Solution 3:

To ease up the time complexity of searching I used STL map.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,pair<int,bool>>mp;
        for(int i=0;i<nums.size();i++)
            mp[nums[i]]={i,true};
        
        for(int i=0;i<nums.size();i++){
            if(mp[target-nums[i]].second==true && i!=mp[target-nums[i]].first){
                int tmp=mp[target-nums[i]].first;
                return {i,tmp};
            }
        }
        
return nums;
    }
};

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