@JohnRennie Hello.i just wanted to know if u code machine learning stuffs too?

Ah you mean AI stuff.

yea

I have done a bit of it with Satan29, but mainly just following instructions to do simple ML tasks. It's not something I know very much about.

But I can probably help you with instructions for installing and getting it working.

ahh ok

@JohnRennie are u free

Yes

i had adoubt

i am supposed to find three numbers in an array whose sum is equal to a target sum given

something like this:

[12, 3, 1, 2, -6, 5, -8, 6]-array

0-targetsum

[12, 3, 1, 2, -6, 5, -8, 6]-output

i tried a hashmap for this:

def threeNumberSum(array, targetSum):
    hashtable={}
    output=[]

    for i in range(len(array)-1):
        hashtable[array[i]]=True


    for i in range(len(array)-1):
        for j in range(len(array)-1):
            if i==j:
                continue
            y=targetSum-array[i]-array[j]
            if y in hashtable and (y!=array[i] and y!=array[j]):
                output.append(sorted([array[i],array[j],y]))


    return output

print(threeNumberSum([12, 3, 1, 2, -6, 5, -8, 6],0))

but this is giving me duplicates

do u know a way to remove duplicates here

I'm not sure what your algorithm is ...

i select two numbers using for loop

array[i] and array[j]

so the thirdnumber has to be targetsum-array[i]-array[j]

Then you look up that number to see if it's in the has table.

yes

And you're using the hash table because it's faster than using a third loop?

yea

In general there will be duplicates i.e. there will be more than one set of three numbers that have the required sum.

Do you have to return all such sets or just the first set you find?

wait i posted wrong picture of output

output should be:

D:\rhs\Python>python test.py
[[-8, 3, 5], [-8, 3, 5], [-6, 1, 5], [-6, 1, 5], [-6, 1, 5], [-6, 1, 5], [-8, 3, 5], [-6, 1, 5], [-6, 1, 5], [-8, 3, 5], [-8, 3, 5], [-8, 3, 5]]

Ah, I see what you mean.

yea

don't want those duplicates

also [-8,2,6] is left out

i dont know why

D:\rhs\Python>python test.py
[[3, 5, -8], [3, -8, 5], [1, -6, 5], [1, 5, -6], [-6, 1, 5], [-6, 5, 1], [5, 3, -8], [5, 1, -6], [5, -6, 1], [5, -8, 3], [-8, 3, 5], [-8, 5, 3]]

That's what I get if I remove the sort.

So you are finding the combinations in different orders.

yea

    for i in range(len(array)-1):
        for j in range(len(array)-1):

In the inner loop you don't have to start at [0] because you've already looked at that number in the first loop. You can start the inner loop at i+1.

ok

Also, shouldn't the range by len(array) not len(array)-1?

ah yea

my bad

now it works properly

:-)

just have to solve for duplicates

The problem is that in the hashtable you are also starting at 0 rather than j.

yea

It might be simplest to just remove the duplicates from the output list.

def threeNumberSum(array, targetSum):
    hashtable={}
    output=[]

    for i in range(len(array)-1):
        hashtable[array[i]]=True


    for i in range(len(array)):
        for j in range(len(array)):
            if i==j:
                continue
            y=targetSum-array[i]-array[j]
            if y in hashtable and (y!=array[i] and y!=array[j]):
                solution=sorted([array[i],array[j],y])
                if solution not in output:
                    output.append(solution)

this works now

OK :-)

:)

Is this a Code Forces problem?

no leetcode

OK. They may present you with very long arrays where your strategy takes too long.

Try it and see I guess.

ok

@JohnRennie one doubt

my code is accepting i==j case also

like for this example:

def threeSum(array):
            hashtable={}
            output=[]

            for i in range(len(array)-1):
                hashtable[array[i]]=True


            for i in range(len(array)):
                for j in range(len(array)):
                    if i==j:
                        continue
                    y=array[i]-array[j]
                    if y in hashtable and (y!=array[i] and y!=array[j]):
                        solution=sorted([array[i],array[j],y])
                        if solution not in output:

I am getting:

[[-1, -1, 0], [-1, 0, 1], [-1, 1, 2]]

the first item in output list is only possible when i==j case

but my if case should have avoided it

I'd guess you're getting the duplicate from the hash table.

That's because you're searching the whole hash table including entries you've already looked at.

ohh

ahh

-1-(-1) is giving 0

we needed 2

finally got my mistake

OK :-)

@JohnRennie I am failing at 315th testcase out of 318

i guess this is too slow

they really gave a big array

Yes, they tend to deliberately present a really large dataset to check the students are using a fast algorithm.

in the hints they have given fix two numbers and use hash map

i don't know how else we can optimise this .

i guess i need to check solution only

I'm in the middle of doing something I'm afraid.

ohk

@Aladdin If you post the link to the web page with the problem I'll have a look as soon as I'm free.

ohk

leetcode.com/problems/3sum

my solution is:

class Solution:
    def threeSum(self, array: List[int]) -> List[List[int]]:
        hashtable={}
        output=[]

        for i in range(len(array)):
            hashtable[array[i]]=i


        for i in range(len(array)):
            for j in range(len(array)):
                if i==j:
                    continue
                y=0-(array[i]+array[j])
                if y in hashtable and (hashtable[y]!=i and hashtable[y]!=j):
                    solution=sorted([array[i],array[j],y])
                    if solution not in output:

OK, I'll have a look as soon as I'm free

thank you

@Aladdin I got a bit further using a dictionary to check for duplicates:

class Solution:
    def __init__(self):
        self.dups = {}

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        hashtable={}
        output=[]

        for i in range(len(nums)):
            hashtable[nums[i]]=i

        for i in range(len(nums)):
            for j in range(len(nums)):
                if i==j:
                    continue
                y=0-(nums[i]+nums[j])
                if y in hashtable and (hashtable[y]!=i and hashtable[y]!=j):
                    solution=sorted([nums[i],nums[j],y])

@JohnRennie I think u nearly solved this! i will ask u about this tommorow

@Aladdin I think I've figured out how to solve it. The failing case has lots of the same number, i.e. 0, so it's triggering lots of duplicate checks and that is using up the time.

But we are only taking three numbers, so there is no point in the list having more than three zeroes or more than two identical non-zero numbers. So at the start we should process the list and remove unnecessary extra numbers. This can be done when you're building the hash table at the start.

Done it! :-)

This is the code. We can discuss how it works whenever you want.

class Solution:
    def threeSum(self, nums):
        output=[]

        # Find the number of occurrences of each number
        hashtable={}
        for num in nums:
            if not num in hashtable:
                hashtable[num] = 1
            elif num != 0 and hashtable[num] < 2:
                hashtable[num] += 1
            elif num == 0 and hashtable[num] < 3:
                hashtable[num] += 1

        # Build a new list of the numbers in the hash table but with no
        # more than three occurrences of each number