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
}

Uh oh!