Find 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] 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]
Constraints:
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109
Check out the java section the runtime for this problem is 4 ms of runtime
🔰Solution in JavaScript
MY First approach:-->
its a very basic approach using loops .
we have given an array of nums and the target value we have to find indices of two number when the sum of array of two indices is equal to target .
Here we are using loop so my first loop start with i and goes up to nums.length-1(last index) and my second loop will start from j=i+1
why j=i+1 because we are adding the two indices
if i=0 then j=i+1=>1index 0=2 and index 1=7;
so the sum=nums[i] +nums[j] =9 now we have to compare with it to the target so our target is 9 . so loops continue till the condition is true and compare it with the target and if the target matches it will return the indices
Var twoSum = function(num,target){
for(let i=0; i<nums.length-1; i++) {
for(let j=i+1: j<=nums.length-1; j++){ if(nums[i] + nums[j] == target){
retrun[i,j];
}
}
};
Note: The Runtime for the upper code is 120 Seconds
🔰Second Approach Solution in Javascript
In the second approach, we are going to use the map and 'for loop' for the solution of the problem Here we are using a map and for loop
var twoSum = function ( nums, target ) {
let map =newMap ;
for ( let i=0; i<nums.length: i++ ) {
let complement = target - nums [i];
if ( map.has( complement)) {
retrun[ map.get(complement), i]
}
map.set(nums[i],i)
}
};
Note: Runtime for this solution is 72 ms
🔰 Solution in Java
Now the solution in java language you can solve this problem in multiple ways so here the solution is in two approaches the first approach is very simple as there is no time consideration and it is implementation based but the second approach is going to take consideration of time complexity .
so let's start
1. First approach
Here we are solving through basically using loops and very simple logic
class Solution {
public int[] twoSum(int[] nums, int target) {
int s=0;
int[] a = new int[2];
for(int i=0;i<nums.length;i++){ for(int j=0;j<nums.length;j++){
if(i != j)
s = nums[i] + nums[j];
if(s == target){
a[0] = i;
a[1] = j;
break; } } } return a; } }
Note: This approach takes 134 s of Runtime and it is not an optimized code
Second approach
Solving problems using Hashmap
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; ++i){
if(map.containsKey(nums[i])) return new int[] {map.get(nums[i]).intValue(), i};
map.put(target - nums[i], i);
} return null;
}
}
Note: Then Runtime we get from this approach is 4ms.
🔰Solution in Python 3
First approach
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
check = {}
for i in range(len(nums)):
if nums[i] in check.keys():
return [i,check[nums[i]]]
check[target-nums[i]]=i
}
map.set(nums[i],i)
}
};
Note: Runtime for this solution is 72 ms
🔰 Solution in Java
Now the solution in java language you can solve this problem in multiple ways so here the solution is in two approaches the first approach is very simple as there is no time consideration and it is implementation based but the second approach is going to take consideration of time complexity .
so let's start
1. First approach
Here we are solving through basically using loops and very simple logic
class Solution {
public int[] twoSum(int[] nums, int target) {
int s=0;
int[] a = new int[2];
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums.length;j++){
if(i != j)
s = nums[i] + nums[j];
if(s == target){
a[0] = i;
a[1] = j;
break;
}
}
}
return a;
}
}
Note: This approach takes 134 s of Runtime and it is not an optimized code
Second approach
Solving problems using Hashmap
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; ++i){
if(map.containsKey(nums[i])) return new int[] {map.get(nums[i]).intValue(), i};
map.put(target - nums[i], i);
}
return null;
}
}
Note: Then Runtime we get from this approach is 4ms.
🔰Solution in Python 3
First approach
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
check = {}
for i in range(len(nums)):
if nums[i] in check.keys():
return [i,check[nums[i]]]
check[target-nums[i]]=i
Note: The Runtime for this approach 105ms.
🔰 Solution in C++
Check out the solution in C++ programming language.
First
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < nums.size(); i++)
if (hash.count(target - nums[i]))
{
result.push_back(hash[target - nums[i]]);
result.push_back(i);
return result;
}
else
hash[nums[i]] = i;
return result;
}
};
Note: The Runtime for this problem is 24 ms
Second approach
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
int size = nums.size();
if(size==0)
{
return ret;
}
unordered_map <int,int> map;
for (int i = 0; i < size; i++)
{
auto itr = map.find(target-nums[i]);
if (itr != map.end())
{
ret.push_back(itr->second);
ret.push_back(i);
return ret;
}
else {
map.insert({nums[i],i});
}
}
return ret;
}
};
Note: the runtime for this approach is 15 ms
The purpose here to know about the runtime or time complexity is to make the code more efficient and fast so that the time taken by the website should be less or the website load quickly due which the user engagement increase and users love to visit again and again. so there majority two approaches first one is loop-based i.e Nested loop and the hash table. If we are using a nested loop which generally takes O(n^2) time so we are using has a table- ta map every value with its index as a key, and value pair until we reach a number which is the difference between the target and the number is currently processed. for now, we check at every iteration whether the value equalling the target minus the current number has already been saved.
Third approach
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map<int,int> store;
for(int i = 0; i < nums.size(); ++i)
{
auto itr = store.find(nums[i]);
if(itr != store.end())
return std::vector<int> {itr->second+1,i+1};
else
store[target-nums[i]] = i;
}
}
};
Try also
Tags:
programming