O(n^2) solution by three pointers in python


  • 0
    L
    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            sort_nums = sorted(nums)
            list = []
            
            for left in range(len(sort_nums)-2):
                if sort_nums[left] >0:
                    break
                if left>=1 and sort_nums[left] == sort_nums[left-1]:
                    continue
                mid = left +1
                right = len(sort_nums) -1
                while mid<right:
                    tmp = 0 - sort_nums[left]
                    if sort_nums[mid] + sort_nums[right] == tmp:
                        list.append([sort_nums[left], sort_nums[mid], sort_nums[right]])
                        mid +=1
                        right -= 1
                        while mid<right and mid >=1 and sort_nums[mid] == sort_nums[mid -1]:
                            mid += 1
                        while mid<right and right <len(sort_nums)-1 and sort_nums[right] == sort_nums[right+1]:
                            right -= 1
                    elif sort_nums[mid] + sort_nums[right] > tmp:
                        right -= 1
                    else:
                        mid += 1
            return list
    

Log in to reply
 

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