611. Valid Triangle Number

Leetcode link

题目简介

本题给了一个数组 nums 要求我们在数组中任意选取三个数字组成一个三角形，并且求出三个数字的组合有多少种

如果有两个数组元素相等，也视为两个不同的元素

解题思路

要组成三角形的要求就是两边之和大于第三边

我们可以先对数组升序排序，然后我们用下标 k 由后往前遍历数组（从大到小）

遍历的过程中，我们需要用双指针 i, j 来分别指向 0 以及 k-1

接下来我们计算 nums[i] + nums[j] > nums[k] ，有两种可能：

• true 代表当前组合可以组成三角形，那么我们可以组成三角形的组合数 count 需要加上 j-i 种（因为如果 i 可以组成三角形，比 i 大且比 j 小的数组元素也能够组成三角形）
• false 代表当前组合无法组成三角形，那么我们可以将 i++ 来寻找更大的数组元素

当我们完成下标 k 的遍历时，组合数 count 就是答案

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
    let count = 0
    nums.sort((a, b) => a - b)
    for(let k = nums.length - 1;k>=0;k--) {
        let i = 0, j = k - 1
        while(i < j) {
            if(nums[i] + nums[j] > nums[k]) {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    return count
};