@JohnRennie Hello

@Aladdin Hi :-)

if you are free ,can u explain ur code

Your code was working fine, and you can see that I've left your code mostly unchanged. I just added two things:

Firstly I removed unnecessary repeats of numbers in the input list.

Suppose your input list is [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Then the only triple that sums to zero is '[0, 0, 0]`. Yes?

And no matter how many zeroes there are we can only ever have three of them in the output.

yea

So if there are more than three zeroes in the input list we can remove the extra ones leaving only three.

And for non-zero numbers we can only have two of the same number appear in a triple.

e.g. suppose the input is [2, 2, 2, 2, 2, 2, 2, 2, 2, -1, -1, -1, -1, -1, -1, -1, -1]

The only possible output is [2, -1, -1]

yes

that makes sense

So we can shrink the list down to [2, 2, -1, -1] without changing the output.

yea

That's what this code does:

        # 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
        newlist = []
        for num in hashtable:

if not num in hashtable:
                hashtable[num] = 1

shouldn't it be : if num not in hashtable?

Either form works.

ah ok

Can you see how this works?

yes

it gets occurances of the numbers in the array and stores it in hashmap

Yes, so the dictionary ends up with an entry for every number that appears in the input list and a count of how many times that number appears, but that count is limited to 2 for non-zeros and 3 for zero.

yea

then using that u build the sorted array

Then the next chunk:

and use hashmap on it

        # Build a new list of the numbers in the hash table but with no
        # more than three occurrences of each number
        newlist = []
        for num in hashtable:
            for i in range(hashtable[num]):
                newlist.append(num)
        newlist = sorted(newlist)

Recreates the input string from the dictionary.

yep

what does dups do?

So now newlist contains all the numbers from the input, but it limits the number of duplicates to 2 for non-zeroes and 3 for zeroes.

ok

dups is another dictionary/hash table.

In Python you can use a surprising large range of types as keys in a dictionary.

When working with the hashtable dictionary we are using an integer as the key, but you can also use a tuple of three numbers as a key.

oh nice

So I could write dups[(1,2,3)] = true to add the key (1,2,3) to the dictionary with the value true.

that makes sense

So this is an easy way to check for duplicate tuples.

Unfortunately you cannot use a list [1,2,3] as a key, so that's whi you see me converting the list to a tuple in the code so I can use it as a key.

ohk

Using a dictionary to check for duplicates tuples is very fast. Much faster than using if mylist in outputlist.

yep

one last doubt

And those two changes did the trick! :-)

yea your solution is very clever

            if y in hashtable and hashtable[y] > j:

can u tell me why u used hashtable[y]>j

Note that I'm using:

for i in range(len(newlist)):
    for j in range(i+1, len(newlist)):

So j is always greater than i. Yes?

yes

And hashtable[y] is the index of the third number i.e. effectively k if we did:

    for i in range(len(newlist)):
        for j in range(i+1, len(newlist)):
            for k in range(j+1, len(newlist)):

So all we need to check is that hashtable[y] > j.

ohhk

that makes sense

thanks a lot!

i can try the code now

:-)