Why is my method creating an extra list within a list? Leetcode 3Sum question-CodePudding

This is a solution for leetcode 3sum problem: https://leetcode.com/problems/3sum/

I think I have a solution, might be slow but nonetheless a solution. But I cant seem to figure out why I keep getting an extra list. Basically for the input:nums = [-1,0,1,2,-1,-4] Ishould get back from my code the output: [[-1,-1,2],[-1,0,1]]. But instead I am getting: [[-1, 2, 1], [-1, 1, 0], [-1, 1, 0]]. I tried using this to remove the duplicate list, but I think there is some logical error being made to cause this extra list. Here is that code to remove duplicate lists within list, wasn't giving any useful output, just memory location:

dup_set = set(map(tuple,a))
non_dup_set = map(list,dup_set)

Was also thinking I might need a hashmap so that the method knows not to re-use indexes but my understanding of hashmaps is not that good, I just think key-values, but nothing beyond that.

Here is the full code:

class Solution:
    def threeSum(self, nums):
        nums.sort()
        l = 0
        r = len(nums) - 1
        final_list = []
        
        while l < r:
            if nums[l]   nums[r] <= 0:
                print(nums[l 1:r])
                if (nums[l]   nums[r]) in nums[l 1:r]:
                    final_list.append([nums[l],nums[r],(nums[l] nums[r])])
                l =1
            elif nums[l]   nums[r] >= 0:
                print(nums[l 1:r])
                if -(nums[l]   nums[r]) in nums[l 1:r]:
                    final_list.append([nums[l],nums[r],(nums[l] nums[r])])
                r-=1

        print(final_list)
            
            
Solution().threeSum([-1,0,1,2,-1,-4])

Output: [[-1, 2, 1], [-1, 1, 0], [-1, 1, 0]]

Desired: [[-1, 2, 1], [-1, 1, 0]]

Please help Thank you

CodePudding user response：

I think you can go like this:

non_dup_set = list(set(map(tuple, a)))

CodePudding user response：

Consider this answer. It gets the right tuples, although not in the same order. Not sure why that should matter.

class Solution:
    def threeSum(self, nums):
        final_list = []
        for l, v1 in enumerate(nums):
            for r, v2 in enumerate(nums[l 1:]):
                if -(v1 v2) in nums[l r 1:]:
                    check = sorted((v1,v2,-(v1 v2)))
                    if check not in final_list:
                        final_list.append(check)
        print(final_list)

Solution().threeSum([-1,0,1,2,-1,-4])

An even better answer uses itertools.combinations to simplify things:

import itertools
class Solution:
    def threeSum(self, nums):
        final_list = []
        for subset in itertools.combinations(nums,3):
            if sum(subset) == 0:
                check = sorted(subset)
                if check not in final_list:
                    final_list.append(check)
        print(final_list)

Solution().threeSum([-1,0,1,2,-1,-4])

And the obligatory one-liner:

import itertools
class Solution:
    def threeSum(self, nums):
        final_list = list(set(tuple(sorted(subset)) for subset in itertools.combinations(nums,3) if sum(subset) == 0))
        print(final_list)

Solution().threeSum([-1,0,1,2,-1,-4])