leetcode

README

611. 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 这一个不等式是否成立即可。

代码

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
}