Two sum equal to target

Question

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

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 25-Jul-21 16:52pm

_-_-_-me

Updated 1-Jan-22 2:39am

v3

Add a Solution

Comments

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.

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Rick York · Answer 1 · 2021-07-25T17:45:00

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.

Patrice T · Answer 2 · 2021-07-25T19:30:00

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.

Member 15485755 · Answer 3 · 2022-01-01T02:39:00

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

Posted 1-Jan-22 2:39am

Member 15485755

Member 15398745 · Answer 4 · 2021-10-18T07:49:00

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;

Posted 18-Oct-21 7:49am

Member 15398745

Comments

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)".