题目大意

解题思路

首先明确什么条件一定能组成三角形？

  • a + b > c (c为最长边)

Code

  1. class Solution {
  2. public:
  3.     int triangleNumber(vector<int>& nums) {
  4.         int ans = 0;
  5.         if (nums.size() < 3) return ans;
  6.         sort(nums.begin(), nums.end());
  7.         for (int i=0;i<nums.size()-2;i++) {
  8.             for (int j=i+1;j<nums.size()-1;j++) {
  9.                 int l = j+1, r = nums.size()-1, k = j; // k = j 假如二分没有找到符合的k，j-j也不影响。
  10.                 while (l <= r) {
  11.                     int mid = (l+r)/2;
  12.                     if (nums[mid] < nums[i] + nums[j]) {
  13.                         k = mid;
  14.                         l = mid + 1;
  15.                     }
  16.                     else {
  17.                         r = mid - 1;
  18.                     }
  19.                 }
  20.                 ans += k - j;
  21.             }
  22.         }
  23.         return ans;
  24.     }
  25. };

法二

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