0611. 有效三角形的个数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 双指针

1. 📝 题目描述

• leetcode

给定一个包含非负整数的数组 nums，返回其中可以组成三角形三条边的三元组个数。

---

示例 1：

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2：

输入: nums = [4,2,3,4]
输出: 4

---

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

2. 🎯 s.1 - 排序 + 双指针

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int triangleNumber(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int count = 0;
    for (int k = numsSize - 1; k >= 2; k--) {
        int i = 0, j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
    }
    return count;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function (nums) {
  nums.sort((a, b) => a - b)
  let count = 0
  for (let k = nums.length - 1; k >= 2; 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
}

py

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        count = 0
        for k in range(len(nums) - 1, 1, -1):
            i, j = 0, k - 1
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    count += j - i
                    j -= 1
                else:
                    i += 1
        return count

• 时间复杂度：$O(n^2)$，其中 n 是数组长度
• 空间复杂度：$O(\log n)$，排序的栈空间

算法思路：

• 排序后固定最大边 nums[k]，用双指针 i、j 在左侧寻找满足 nums[i] + nums[j] > nums[k] 的组合
• 当满足条件时，i 到 j-1 之间的所有值与 nums[j] 配对都有效，一次计入 j - i 个