# [611. Valid Triangle Number](https://leetcode.com/problems/valid-triangle-number/)

## 题目

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

## 题目大意

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

## 解题思路

- 题意很简单，最容易想到的暴力解法是三重循环，暴力枚举，时间复杂度 O(n^3)。三重循环中最内层的循环可以优化，因为 k 和 i，j 存在关联性。第二层循环 j 从 i + 1 开始循环，k 从 j + 1 = i + 2 开始循环。循环累加 k 的值，直到 `nums[i] + nums[j] > nums[k]`，那么 `[nums[j + 1], nums[k - 1]]` 这个区间内的值都满足条件。满足条件的解个数增加 `k - j - 1` 个。j 再次递增 + 1，此时最内层的 k 不用从 j + 1 开始增加，只用从上次 k 开始增加即可。因为如果 `nums[i] + nums[j] > nums[k]`，如果这个 `nums[i] + nums[j + 1] > nums[m + 1]` 不等式成立，那么 m 一定不小于 k。所以内层循环 k 和 j 加起来的时间复杂度是 O(n)，最外层 i 的循环是 O(n)，这样优化以后，整体时间复杂度是 O(n^2)。
- 可能有读者有疑问，三角形三条边的组成条件：任意两边之和大于第三边。`a + b > c`，`a + c > b`，`b + c > a`，此处为什么只判断了 `a + b > c` 呢？因为一开始进行了排序处理，使得 `a ≤ b ≤ c`，在这个前提下，`a + c > b`，`b + c > a` 是一定成立的。所以原问题便转化为只需关心 `a + b > c` 这一个不等式是否成立即可。此题的测试用例用有一种特殊情况，那就是其中一条边或者两条边长度为 0，那么 `a + b > c` 这个不等式一定不成立。综上，先排序预处理之后，只需要关心 `a + b > c` 这一个不等式是否成立即可。

## 代码

```go
package leetcode

import "sort"

func triangleNumber(nums []int) int {
	res := 0
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		k := i + 2
		for j := i + 1; j < len(nums)-1 && nums[i] != 0; j++ {
			for k < len(nums) && nums[i]+nums[j] > nums[k] {
				k++
			}
			res += k - j - 1
		}
	}
	return res
}
```