611. 有效三角形的个数

Difficulty
Medium
Tags
双指针
URL
https://leetcode.cn/problems/valid-triangle-number/
Star
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:
输入: nums = [4,2,3,4]
输出: 4
提示:
  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

法 1

思路：三数之和通过排序后，使得 数值和 具有了单调性，因此可以通过和 target 比大小，来缩减搜索空间，即如果大于target了，r -= 1，如果小于target，则 l += 1， 最终达到优化时间复杂度的目的。
但是本题是要组成三角形的三条边，即使判断出 nums[i], nums[l], nums[r] 无法组成三角形也不知道应该如何缩小搜索空间，所以直接用三数之和的方法肯定不行。但是思路可以借鉴，即找到一个单调性，例如，如果有： nums[i], nums[l], nums[r] 可以组成三角形，则nums[i] nums[l+1], nums[r-1]也一定能行 这样的性质，那么就可以很容易的缩减搜索空间。
假设 nums 为有序数组，显著固定一条最长边 nums[i]
  • 如果 nums[l] + nums[r] > nums[i]，即两短边之和大于了长边，那么一定可以组成三角形，现在如果一直增加另外一条边 nums[l]，那必然依旧满足 nums[l] + nums[r] > nums[i]，因此还能组成三角形。
  • 如果 nums[l] + nums[r] ≤ nums[i]，说明两条短边之和太短，需要增加其。
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]:
                    res += r - l
                    r -= 1
                else:
                    l += 1

        return res

法 2

对变成排序后，固定两条短边，然后找大于等于这两条短边之和的最小边，那么数组中大于该最小边的数字也一定能组成三角形。
时间复杂度为O(n^2)
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        res = 0
        nums.sort()
        for i in range(0, len(nums)-2):
            for j in range(i+1, len(nums)-1):
                temp = nums[i] + nums[j]
                # 找 小于 temp 最大值的下标
                l,r = j+1, len(nums)-1
                while l <= r:
                    m = l + (r - l) // 2
                    if nums[m] >= temp:
                        r = m -1
                    else:
                        l = m + 1
                
                res += r - j
                    

        return res