What is the flaw in my solution for 3Sum?-CodePudding

I'm trying to solve 3Sum on Leetcode and my code is as follows.

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
    ans = {}

    # iterate over each num, setting -num as target
    for index, target in enumerate(nums)
        target = -target
        nums.pop(index)
        ht = {}
        
        for num in nums: 
            # when a match is found, sort it and insert as a tuple to get rid of duplicates in hash table
            if num in ht: 
                ans[tuple(sorted([-target, num, target - num]))] = None
            
            else:
                ht[target-num] = num
        
    return list(ans.keys())

This works for 247/311 cases, and I can't seem to figure out why not all. Any help on pointing out flaws in my logic would be appreciated! Thanks in advance!

Test case as requested:

Input

[34,55,79,28,46,33,2,48,31,-3,84,71,52,-3,93,15,21,-43,57,-6,86,56,94,74,83,-14,28,-66,46,-49,62,-11,43,65,77,12,47,61,26,1,13,29,55,-82,76,26,15,-29,36,-29,10,-70,69,17,49]

My output

[[-49,15,34],[-82,34,48],[-70,34,36],[-43,-3,46],[-82,36,46],[-14,2,12],[-49,2,47],[-3,1,2],[-43,12,31],[-70,-14,84],[-49,-3,52],[-82,-11,93],[-49,21,28],[-82,21,61],[-70,21,49],[-43,-14,57],[-70,13,57],[-43,15,28],[-29,1,28],[-29,-14,43],[-66,-11,77],[-82,26,56],[-43,17,26],[-14,1,13],[-49,13,36],[-82,13,69],[-49,-6,55],[-70,15,55],[-70,-6,76],[-43,10,33],[-66,10,56],[-11,1,10],[-66,-3,69],[-70,1,69],[-43,-6,49],[-82,33,49],[-66,17,49]]

Expected output

[[-82,-11,93],[-82,13,69],[-82,17,65],[-82,21,61],[-82,26,56],[-82,33,49],[-82,34,48],[-82,36,46],[-70,-14,84],[-70,-6,76],[-70,1,69],[-70,13,57],[-70,15,55],[-70,21,49],[-70,34,36],[-66,-11,77],[-66,-3,69],[-66,1,65],[-66,10,56],[-66,17,49],[-49,-6,55],[-49,-3,52],[-49,1,48],[-49,2,47],[-49,13,36],[-49,15,34],[-49,21,28],[-43,-14,57],[-43,-6,49],[-43,-3,46],[-43,10,33],[-43,12,31],[-43,15,28],[-43,17,26],[-29,-14,43],[-29,1,28],[-29,12,17],[-14,-3,17],[-14,1,13],[-14,2,12],[-11,-6,17],[-11,1,10],[-3,1,2]]

Ran a script to get the diff of

[-82, 17, 65], [-66, 1, 65], [-49, 1, 48], [-29, 12, 17], [-14, -3, 17], [-11, -6, 17]

CodePudding user response：

The problem is the line nums.pop(index)because it doesn't actually delete the right index.
After the first iteration, index will be equal to 1 but the second element is actually the third in the original list, example below:

[1,2,3,4] #index = 0
[2,3,4] #index = 1 
 #now we see that 3 will be deleted instead of 2

We can correct that by looping over the elements after the current one instead of deleting it:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = {}

        # iterate over each num, setting -num as target
        for index, target in enumerate(nums):
            target = -target
            ht = {}

            for num in nums[index 1:]: #loop over the elements from index 1 on so we don't duplicate
                # when a match is found, sort it and insert it as a tuple to get rid of duplicates in the hash table
                if num in ht: 
                    ans[tuple(sorted([-target, num, target - num]))] = None

                else:
                    ht[target-num] = num

        return list(ans.keys())

Which works just fine