LeetCode-Solutions/Python/valid-triangle-number.py at master · pythonpeixun/LeetCode-Solutions · GitHub

21 lines (19 loc) · 514 Bytes

# Time: O(n^2)

# Space: O(1)

class Solution(object):

def triangleNumber(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

result = 0

nums.sort()

for i in xrange(len(nums)-2):

if nums[i] == 0:

continue

k = i+2

for j in xrange(i+1, len(nums)-1):

while k < len(nums) and nums[i] + nums[j] > nums[k]:

k += 1

result += k-j-1

return result

Expand file tree