611. Valid Triangle Number

Information

  • Diffculty: Medium

  • Created: 2019-08-31 18:17:08

  • Last Motified: 2019-08-31 18:17:08

Solution

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        nums = [n for n in nums if n != 0]
        i = 0
        ans = 0
        for k in range(len(nums) - 1, 1, -1):
            i = 0
            for j in range(k - 1, 0, -1):
                if i >= j:
                    break
                while i < j and nums[i] + nums[j] <= nums[k]:
                    i += 1
                ans += j - i
        return ans