611. 有效三角形的个数

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

1. 数组长度不超过1000。
2. 数组里整数的范围为 [0, 1000]。

数组 二分 中等

代码

1. 排序+二分(O(n^2logn))

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

2. 排序+双指针

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

3. 排序

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        # 从大到小遍历
        for i in range(len(nums) - 1, 1, -1):
            l, r = 0, i -1
            while l < r:
                # 只要较小的两个值之和大于最大的值，则一定可组成三角形
                if nums[l] + nums[r] > nums[i]:
                    #i, r 和从l到r-1都可组成三角形，个数为 (r-1) - l + 1 = r - l
                    res += (r-1) - l + 1
                    r -= 1
                else: 
                    l += 1
        return res