有效三角形的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int ans = 0;
    // i 指向最长的边
    for (int i = 0; i < n; i++) {
      // j 指向第二长的边
      for (int j = i - 1, k = 0; k < j; j--) {
        // k 指向最短的边
        while (k < j && nums[k] + nums[j] <= nums[i]) k++;
        ans += j - k;
      }
    }
    return ans;
  }
};