`for`

loops to do this.
15,169,069 members

See more:

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

target=100000000

AddressSanitizer:DEADLYSIGNAL

=================================================================

==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffdad19f378 (pc 0x55791e218052 bp 0x7ffdb30fc410 sp 0x7ffdad19e380 T0)

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

==30==ABORTING

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.

C++

Copy Code

/** * 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; }

Comments

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.
Comments

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!

In the question , they also given that to write the code with time complexity less than O(n square) .

Thank you!

Use **Improve question** to update your question.

So that everyone can pay attention to this information.

So that everyone can pay attention to this information.

Okay .

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

Comments

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 !

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 !

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 .

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 .

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!

Does the solution becomes easy when we know different language such as java, c++ ?

or

Does it not depend?

Thank you!

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 :)

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 :)

Copy Code

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;

Comments

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

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 !