DEV Community

Cover image for 1. Two Sum
Jyotirmoy Barman
Jyotirmoy Barman

Posted on • Updated on • Originally published at jyotirmoy.hashnode.dev

1. Two Sum

Question

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].
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 2 <= nums.length <= 10<sup>4</sup>

  • -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

  • -10<sup>9</sup> <= target <= 10<sup>9</sup>

  • Only one valid answer exists.

Answer

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

The solution we will be using is brute force, the function takes two variables one is nums which contain the vector and the other one is a target which we need to find by summing two indexes in the vector and if we got the sum we will return the index in a new vector.

Before we start the for loops first we need to make an empty vector, which we will call ans. we will use a nested for loop to check if the target is present in the array. The first loop starts with the i'th which is 0 and stops at (vector size - 1) and the inner for loop starts at i+1 and stops as same as (vector size -1), if the index i and i+n (where n is a number less than vector size but greater than i) is equal to the target value we will push the index to the new array ans and return it. It has O(n^2) time complexity as it has two nested loops. Below you can see an animation of how this program works.

Top comments (0)