排序数组枚举+双指针。

代码

1
2
3
4
5
6
7
8
9
10
11
def triangleNumber(self, nums: List[int]) -> int:
    n = len(nums)
    res = 0
    nums.sort()
    for i in range(n):
        j, k = i - 1, 0
        while j > k:
            while j > k and nums[j] + nums[k] <= nums[i]: k += 1
            res += j - k
            j -= 1
    return res