题目描述

链接。

给定一个包含非负整数的数组 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

思路

常规思路，先排序，用两个下标选中两个标，找第三个边的边界。

/**
 * @file   611.cpp
 * @brief
 * @author zhenkai.sun
 * @email  zhenkai.sun@qq.com
 * @date   Sat Sep 27 10:13:28 AM CST 2025
 */

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
  int bin_search(const std::vector<int>& nums, int l, int r, int target) {
    while (l < r) {
      int mid = (l + r) / 2 + 1;
      if (nums[mid] >= target) {
        r = mid - 1;
      } else {
        l = mid;
      }
    }
    return l;
  }

 public:
  int triangleNumber(vector<int>& nums) {
    int result{0};
    if (nums.size() < 3) return 0;
    std::sort(nums.begin(), nums.end());
    int i = 0;
    while (nums[i] == 0 && i < nums.size()) ++i;
    for (; i < nums.size() - 2; i++) {
      for (int j = i + 1; j < nums.size() - 1; ++j) {
        // 找到 nums[k] < nums[i] + nums[j] 的最大坐标
        int k = bin_search(nums, j, nums.size() - 1, nums[i] + nums[j]);
        result += k - j;
      }
    }
    return result;
  }
};

int main() {
  Solution s;
  std::vector<int> nums{2, 2, 3, 4};
  auto a = s.triangleNumber(nums);
  std::cout << a << std::endl;

  nums = {4, 2, 3, 4};
  a = s.triangleNumber(nums);
  std::cout << a << std::endl;

  nums = {2, 3, 4};
  a = s.triangleNumber(nums);
  std::cout << a << std::endl;
  return 0;
}

/*
 * OUTPUT
wii 🌐 work coding/leetcode  master [?] via C v13.3.0-gcc ❯ mk 611
3
4
1
 * */

二分查找的变体

变体

根据不同的优化条件，调整二分查找的逻辑，可以解决很多二分查找变体问题。

• 查找第一个等于目标值的元素

• 查找最后一个等于目标值的元素

• 查找第一个不小于目标值的元素

• 查找第一个不大于目标值的元素

优化条件

1. 中间点优化

2. 边界条件优化

3. 终止条件优化

固定最大边

还有一个思路，是固定最大边，nums[k] 作为最大边，判断 [0, k] 之间的元素。

• 如果 [l, r] 边界元素和大于最长边，那中间的所有元素都可以和 l 组合形成三边形，共 r - l 个组合

• 如果 [l, r] 边界元素和小于等于最长边，那只能尝试增加 l 边界，因为 r 减小边界和也会减小，然后继续搜索

这种思路的复杂度是 N^2。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int result = 0;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        for (int k = n - 1; k >= 2; --k) {  // 固定最长边
            int l = 0, r = k - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[k]) {
                    result += r - l;  // 所有[l,r]组合都满足
                    r--;
                } else {
                    l++;
                }
            }
        }
        return result;
    }
};