0611. Valid Triangle Number

题目信息

题号:

0611

难度:

Medium

主题:

数组、三角形边长、下标三元组、严格不等式

原题:

LeetCode 0611

重点:

从三个不同下标取边长、三边必须形成非退化三角形、相同数值位于不同下标时仍产生不同组合

题目重述

给定非负整数数组 nums,统计有多少个下标三元组 i < j < k,使 nums[i]、nums[j]、nums[k] 能作为一个三角形的三条边。

三条边必须均为正,并满足任意两边之和严格大于第三边;两边之和恰好等于第三边属于退化情况,不能计数。数组长度位于 [1, 1000],元素位于 [0, 1000]。若相同边长出现在不同数组位置,由不同下标组成的三元组分别计数。

自建示例

同时包含合法与退化组合:

输入:nums = [3,4,5,8]
输出:2
解释:[3,4,5] 和 [4,5,8] 能形成三角形;3+5=8 的组合退化,3+4<8 的组合也不合法。

零不能作为有效边长:

输入:nums = [0,2,2]
输出:0
解释:唯一的下标三元组包含长度为 0 的边,不能形成具有正面积的三角形。