15,171,576 members
1.00/5 (1 vote)
See more:
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.
and
The code should be of time complexity less than O(n square)

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

The input for this is
nums[]=[50000000,3,2,4,50000000]
target=100000000

Error:
=================================================================
#2 0x7f03492de0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
==30==ABORTING

Debugging:

I did debug for other inputs, this code worked fine. But here when I try to debug in this case (input) to find the mistake, The debugging was being stopped itself at the point of creating a hash table.
Is this because in this case, the hash table would be of length 100000000 ?
Is the error also because of that ?
As a hash table of huge length would be created , does that much space available in memmory ?
This code worked in remaining all test cases, but not worked in this one.

What I have tried:

C++
```/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i;
int max=nums[0];
int min=nums[0];
for(i=0;i<numsSize;i++)
{
if(max<nums[i])
{
max=nums[i];
}
if(min>nums[i])
{
min=nums[i];
}
}
int x,y;
int max1=0;
int min1=0;
int largest=max;
int smallest=min;
if(max<0)
{
max1=1;
largest=-1*max;
}
if(min>=0)
{
min1=1;
smallest=-1*min;
}
int hash1[largest+1];         // here I am creating the hashtable of length 100000000
int hash2[(-1*smallest)+1];
i=0;
for(;i<largest+1;i++)
{
hash1[i]=0;
}
i=0;
for(;i<(-1*smallest)+1;i++)
{
hash2[i]=0;
}
i=0;
for(;i<numsSize;i++)
{
if(nums[i]>=0)
{
hash1[nums[i]]++;
}
if(nums[i]<0)
{
hash2[(-1*nums[i])]++;
}
}
i=0;
for(;i<numsSize;i++)
{
if(nums[i]>=0)
{
hash1[nums[i]]--;
}
else
if(nums[i]<0)
{
hash2[(-1*nums[i])]--;
}
if((target-nums[i])>=0)
{
if(max>0 && (target-nums[i])<=max)
{
if(hash1[target-nums[i]]>0)
{
x=i;
y=target-nums[i];
break;
}
}
}
else
if((target-nums[i])<0)
{
if(min<0 && (target-nums[i])>=min)
{
if(hash2[-1*(target-nums[i])]>0)
{
x=i;
y=target-nums[i];
break;
}
}
}
}
*(returnSize)=2;
i=0;
int z=0;
for(;i<numsSize;i++)
{
if(nums[i]==y)
{
z=i;
}
}
int*p=(int*)malloc(2*sizeof(int));
p[0]=x;
p[1]=z;
return p;
}```
Posted
Updated 1-Jan-22 3:39am
v3
Richard MacCutchan 26-Jul-21 3:56am

What is this obsession with hash tables? All you need to do is loop through the list adding every number to every other number until you get the correct sum. A couple of simple loops.
_-_-_-me 27-Jul-21 7:14am

But , it takes O(n square ) complexity. They asked to find with less than O(n square) complexity .
Richard MacCutchan 27-Jul-21 7:21am

Well I still do not understand how you think a hash table will help.
_-_-_-me 28-Jul-21 11:02am

Whenever in the question if they asked to find the solution with less time complexity , I am always using hashmap with out knowing myself.
Because , I am only getting the hash map related idea.
If I think more and more and more... other than hash tag, days are being completed , I am taking 2 days for solving a question , then at last I am always being ended with hash tag.
How could we get the idea on algorithms with less time complexity ?
Thank you !
Richard MacCutchan 28-Jul-21 11:56am

Stop guessing, and find a good resource on algorithms, and study them. Google will find you many resources, and you will learn much faster than posting questions here.

## Solution 1

This problem does not need to use a hash table because the answer has exactly two values in it. You need to calculate the set of your input data combined two at a time. You don't need to retain those values either. Just calculate them once and see if the answer matches. I would make a base 5 counter - however many input values you have, and step through each of them after making sure you don't have matching values. For 5 inputs you will have 25 values minus the possible matches. This amounts to retaining an array of two integers in addition to the input data. You can use nested `for` loops to do this.
_-_-_-me 26-Jul-21 0:02am

Sorry, I forgot to write the complete question .
In the question , they also given that to write the code with time complexity less than O(n square) .
Thank you!
Patrice T 26-Jul-21 0:23am

Use Improve question to update your question.
So that everyone can pay attention to this information.
_-_-_-me 26-Jul-21 0:31am

Okay .

## Solution 2

Quote:
As a hash table of huge length would be created , does that much space available in memmory ?

Hash table, you did it again, already not the solution last time.
You are creating something with large cost to simplify another place of low cost, the result is more cost.
Solve this by hand nums = [2,7,11,15], target = 9
Do you need a hash table ?
Solve this by hand nums[]=[50000000,3,2,4,50000000] target=100000000
Do you need a hash table ?

Just checking every pair is in O(n)= n²

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

[Update]
Quote:
First sorting with time complexity less than O(n square) , and then take two variables , which should be acted as index .
These two indexes , one should start form beginning and other from last of the array .
If the sum is greater than the target , last variable should be decremented.
If the sum is less than target, then the first variable should be incremented...

It is basically the solution, try it ans see how it work.
v2
_-_-_-me 26-Jul-21 3:00am

Okay ,
when I solve this by hand ,
I am solving with the idea same as using the code which takes O(n square) complexity .
In that case , How could we know ?
How can we get the idea of algorithm as simple as possible ?

How could we know that algorithm is:
“Everything should be made as simple as possible, but no simpler.” Albert Einstein

I also got this idea:
First sorting with time complexity less than O(n square) , and then take two variables , which should be acted as index .
These two indexes , one should start form beginning and other from last of the array .
If the sum is greater than the target , last variable should be decremented.
If the sum is less than target, then the first variable should be incremented...

Thank you !
_-_-_-me 26-Jul-21 3:04am

When I solve this by hand,
I am doing it like this,
For every element of the array, I am calculating target-element, and then I am searching whether this value exists or not in the array .
But, this process is taking O(n square) time complexity .
_-_-_-me 26-Jul-21 3:07am

Does the solution also depends up on the language ?
Does the solution becomes easy when we know different language such as java, c++ ?
or
Does it not depend?

Thank you!

## Solution 4

Easy to understand, detailed solution with step by step explanation and code for both brute force and optimized solution:

https://www.code-recipe.com/post/two-sum

Let me know in comments section if you have any doubts. I will be more than happy to answer.

Thank You :)

## Solution 3

```int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2;
int *arr=(int *)malloc(2*sizeof(int));
for(int i=0;i<numsSize;i++)
{
for(int j=i+1;j<numsSize;j++)
{
if(nums[i]+nums[j]==target)
{
arr[0]=i;
arr[1]=j;
break;
}
}
}
return arr;```
Richard Deeming 19-Oct-21 4:25am

Looks like you missed the OP's requirement that the code "should be of time complexity less than O(n square)".