Python O(n^2) solution, 526 ms


  • 1
    W
    def triangleNumber(self, nums):
        nums = sorted(nums)
        total = 0
        for i in range(len(nums)-2):
            if nums[i] == 0:
                continue
            end = i + 2
            for j in range(i+1, len(nums)-1):
                while end < len(nums) and nums[end] < (nums[i] + nums[j]):
                    end += 1
                total += end - j - 1
        return total

Log in to reply
 

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