N^2 Python


  • 0

    First of all, to make all the answers are unique, I choosed a set.

    class Solution(object):
        def threeSum(self, nums):
            answer, ans, dic = set(), [], {}
            nums.sort()
            for i in xrange(len(nums)):
                dic = {}
                for j in xrange(i):
                    if -nums[i] - nums[j] in dic and dic[-nums[j] - nums[i]] < j:
                        if (nums[dic[-nums[j] - nums[i]]], nums[j], nums[i]) not in answer:
                            ans.append([nums[dic[-nums[j] - nums[i]]], nums[j], nums[i]])
                            answer.add((nums[dic[-nums[j] - nums[i]]], nums[j], nums[i]))
                    dic[nums[j]] = j
            return ans
    

    Then, I think in order to make answes unique, I can keep sliding the index until it's different:

    
    class Solution(object):
        def threeSum(self, nums):
            nums.sort()
            i, ans = 0, []
            while i < len(nums) - 2:
                left, right = i + 1, len(nums) - 1
                tmp = nums[i] + nums[left] + nums[right]
                while left < right:
                    tmp = nums[i] + nums[left] + nums[right]
                    if tmp < 0:
                        left += 1
                    elif tmp > 0:
                        right -= 1
                    else:
                        ans.append([nums[i], nums[left], nums[right]])
                        while left < right and nums[left + 1] == nums[left]:
                            left += 1
                        while left < right and nums[right - 1] == nums[right]:
                            right -= 1
                        left, right = left + 1, right - 1
                while i + 1 < len(nums) and nums[i + 1] == nums[i]:
                    i += 1
                i += 1
            return ans
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.