给一个长度为N的非负整数数组nums,请你计算一下,有多少个三元组代表的边长可以组成三角形
数据范围:
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