时间轴

2025-09-26

init

题目：

P611 有效三角形的个数

https://leetcode.cn/problems/valid-triangle-number/description/?envType=daily-question&envId=2025-09-26

此题固定套路是先固定最大的边，然后通过双指针一个从前向后(表示最小边)，一个从后向前(表示次大边)，如果前面那个指针指向的值和后面那个指针指向的值加起来满足了三角形构成条件，那么最小边可以取两个指针之间的任意值，然后可以令次大的边变小些，看是否满足。如果不满足，说明最小的边太小了，让最小的边变大些，因为是最小边，所以其值不能大于次大边。两个指针相遇时，说明已经遍历完了最大边是当前固定的最大边时的情况，此时令最大边小些，然后最小边和次大边重新开始遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <algorithm>
#include <vector>

using std::vector;

class Solution {
public:
  // 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数
  // 1 <= nums.length <= 1000
  // 0 <= nums[i] <= 1000
  int triangleNumber(vector<int> &nums) {
    // 三角形两边之和大于第三边

    if (nums.size() < 3) {
      return 0;
    }
    vector<int> vec(nums);
    int n;
    int i, j, k;
    int res = 0;

    // 排序
    std::sort(nums.begin(), nums.end());
    // 去重,去重前需要先排序
    // vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

    n = vec.size();
    // 先固定最大边,k为三角形中最大的边,其次是j,i是最小的
    for (k = n - 1; k >= 2; k--) {
      i = 0;
      j = k - 1;
      while (i < j) {
        if (nums[i] + nums[j] > nums[k]) {
          // 因为j是从k-1向前遍历,i从0向后遍历
          // 所以如果 nums[i] + nums[j] > nums[k]
          // 所有 [i,j-1] 都和 j, k 可以组成三角形
          res += (j - i);
          --j;
        } else {
          // 不满足三角形构成条件说明i太小了
          // 令i++,直到i==j时退出循环
          // 因为此时k和j固定,任何一个i都无法满足三角形构成条件
          // 说明k太大了,令k--
          i++;
        }
      }
    }
    return res;
  }
};