0611. Valid Triangle Number

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 > ca + c > bb + c > a,此处为什么只判断了 a + b > c 呢?因为一开始进行了排序处理,使得 a ≤ b ≤ c,在这个前提下,a + c > bb + 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
}

⬅️上一页

下一页➡️

Calendar Sep 18, 2021
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者