simple python solution for O(n*n)


  • 0
    N
    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            "at least 3 numbers"
            ret_list = []
            if not nums or len(nums) < 3:
                return ret_list
            
            "sort the numbers"
            nums.sort()
            for i in xrange(len(nums) - 2):
                if nums[i] > 0:
                    break
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                
                j = i + 1
                k = len(nums) - 1
                while j < k:
                    total = nums[i] + nums[j] + nums[k]
                    if total == 0:
                        new_list = [nums[i], nums[j], nums[k]]
                        ret_list.append(new_list)
                        j += 1
                        k -= 1
                        
                        while j < k and nums[k] == nums[k + 1]:
                            k -= 1
                        while j < k and nums[j] == nums[j - 1]:
                            j += 1
                    elif total > 0:
                        k -= 1
                    else:
                        j += 1
            
            return ret_list
    

Log in to reply
 

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