0611._Valid_Triangle_Number.md

611. Valid Triangle Number

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/valid-triangle-number/description/

内容描述

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].

解题方案

思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(1)******

明确一点，三角形三边为a, b, c，那么何时满足可以组成一个三角形呢？ 要同时满足以下3点：

1. a + b > c
2. a + c > b
3. b + c > a

首先对数组逆向排序，固定第一个数字，我们发现nums[i] >= nums[j] >= nums[k], 所以我们现在只需要保证nums[j] + nums[k] > nums[i]即可， 因为nums[i] + nums[j] > nums[k]和nums[i] + nums[k] > nums[j]是肯定的

后面开始二分，分两种情况：

• 如果nums[j] + nums[k] > nums[i]，那么我们只需要将j += 1使得比较式前面变小继续判断， 并且res += k - j，因为组合i, j, [j+1...k]都可以满足比较式，我们需要全部加起来，后面不会再次判断了
• 如果nums[j] + nums[k] <= nums[i]，那么我们只需要将k -= 1使得比较式前面变大继续判断是否满足比较式

class Solution(object):
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        nums = nums[::-1]
        res = 0
        for i in range(len(nums)-2):
            j, k = i + 1, len(nums) - 1
            while j < k:
                if nums[k] + nums[j] > nums[i]:
                    res += k - j
                    j += 1                
                else:
                    k -= 1
        return res

这里真的我遇到了两次坑，首先如果我们排序用的是正向排序的话，那么我们需要做的是固定最后一个数，否则会出现（假如固定第一个数）：

• 等式满足，我们将j -= 1，那么就有可能漏掉了一种情况，就是原本组合i, j, [j+1...k-1]可以满足，但是我们这里没有加上
• 等式满足，我们将k += 1，那么就有可能漏掉了一种情况，就是原本组合i, [j+1...k-1], k可以满足，但是我们这里没有加上

所以二分法真的没有那么简单，我们需要充分根据实际场景去改变我们的固定位置和前后更新方向

这里也给出正向排序的代码：

class Solution(object):
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        res = 0
        for k in range(len(nums)-1, 1, -1):
            i, j = 0, k - 1
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    res += j - i
                    j -= 1
                else:
                    i += 1
        return res