Leecode #611. 有效三角形的个数

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

示例

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

解题思路

最暴力的解法是三层循环，复杂度为O(N^3)是无法通过测试的，更优的解法有二分搜索和双指针法

二分搜索

在第三层遍历的时候采用二分搜索，将复杂度降低到O(N^2logN)

    def triangleNumber(self, nums) -> int:
        import bisect
        N = len(nums)
        count = 0
        nums = sorted(nums)
        for i in range(N-2):
            if not nums[i] :
                continue
            for j in range(i+1, N-1):
                count += bisect.bisect_left(nums, nums[j]+nums[i])-1-j
        return count

这里用bisect模块做二分搜索，奇怪的是bisect_left使用io参数后，速度反而变慢了

双指针

将第二和第三层循环转化为双指针的算法，将时间复杂度降低到O(N^2)且代码更短

def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        for k in range(2, len(nums)):
            l = 0; r = k -1 
            while l < r:
                if nums[l] + nums[r] > nums[k]:
                    res += r - l
                    r -= 1
                else:
                    l += 1
        return res