排序然后 通过bisect找到位置 复杂度 $O(n^2lgn)$

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        pos = bisect.bisect_left(nums, 1)
        nums = nums[pos:]
        ans, n = 0, len(nums)
        for i in range(0,n-2):
            p = i + 2
            for j in range(i+1,n-1):
                p = bisect.bisect_left(nums, nums[i]+nums[j],p,n)
                ans = ans + p -j -1
        return ans

以上算法显示运行时间仅超过20%左右选手，必有蹊跷，故有一个双指针思路的 $O(n^2)$ 算法

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