合法的三角形个数

class Solution:
    def validTriangleNumber(self , nums: List[int]) -> int:
        nums.sort()
        res = 0
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                left, right = j+1, len(nums)-1
                while left <= right:
                    mid = left + (right - left) // 2
                    if nums[mid] < nums[i] + nums[j]:
                        left = mid + 1
                    else:
                        right = mid - 1
                res += left - (j+1)
        return res

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int validTriangleNumber (int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i + 2 < n; i++) {
            for (int j = i + 1; j + 1 < n; j++) {
                int tt = nums[i] + nums[j];
                // 一种通用的二分法，取left和right都在边界外一个
                int left = j, right = n;
                while (left + 1 != right) {
                    int mid = left + (right - left)/2;
                    if (nums[mid] < tt) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                }
                ans += (left - j);
            }
        }
        return ans;
    }
}

import bisect
class Solution:
    def validTriangleNumber(self , nums: List[int]) -> int:
        # write code here
        if len(nums) < 3: return 0        
        count = 0
        nums.sort()
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                count += bisect.bisect_left(nums[j+1:], nums[i]+nums[j])        
        return count