Accepted python solution with O(n^2)


  • 1
    W
    class Solution:
    # @return a list of lists of length 3, [[val1,val2,val3]]
    def threeSum(self, num):
        num.sort()#sort array
        result = []
        length = len(num)
        for n in range(length-2):
            current_n = num[n]
            if n>0 and num[n]==num[n-1]:
                continue
            sum_n = 0-current_n
            low = n+1
            hight = length-1
            while low<hight:
                low_n = num[low]
                hight_n = num[hight]
                if low_n+hight_n<sum_n:
                    low+=1
                    while num[low]==num[low-1] and hight>low:
                        low+=1
                elif low_n+hight_n>sum_n:
                    hight-=1
                    while num[hight]==num[hight+1] and hight>low:
                        hight-=1
                else:
                    result.append([current_n,low_n,hight_n])
                    low+=1
                    while num[low]==num[low-1] and hight>low:
                        low+=1
                    hight-=1
                    while num[hight]==num[hight+1] and hight>low:
                        hight-=1
        return result

  • 0
    P

    I got OLE and TLE error. After reviewing your solution, I figured out my problem and I was through. Thank you very much for sharing.


Log in to reply
 

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