lc.611.有效三角形的个数

​

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

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

解题思路

判断三条边能组成三角形的条件为：

  • 任意两边之和大于第三边，任意两边之差小于第三边。
  • 三条边长从小到大为 a、b、c，当且仅当 a + b > c 这三条边能组成三角形。
 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

class Solution {
public:
bool ok(int a,int b,int c) {
    return (a+b)>c && (c-b) < a;
}
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        if(n<=2) return 0;
        sort(nums.begin(),nums.end());
        int count = 0;
        for(int i=n-1;i>=0;i--) {
            int c = nums[i];
            int l = 0,r = i-1;
            while(l<r) {
                int a = nums[l],b = nums[r];
                if(a+b > c) {
                    count += r-l;
                    --r;
                }else {
                    //<=
                    l++;
                }
            }
        }
        return count;
    }
};

二分法

从后往前找， 最后一个 $nums[mid] > b+c $的数

 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

class Solution {
public:
bool ok(int a,int b,int c) {
    return (a+b)>c && (c-b) < a;
}
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        if(n<=2) return 0;
        sort(nums.begin(),nums.end());
        int count = 0;
        for(int i=0;i<n;i++) {
            for(int j=i-1;j>=0;j--) {
                int b = nums[j],c = nums[i];
                int a;
                int mid;
                int l= 0,r = j-1;
                while(l<r) {
                    mid = (l+r)/2;
                    a = nums[mid];
                    if(a+b>c) {
                        r = mid;
                    }else if(a+b==c) {
                        l = mid+1;
                    }else {
                        //<c
                        l = mid+1;
                    }
                }
                if(l==r &&  nums[r]+nums[j] > nums[i]) {
                    count += j-r;
                }

            }
        }
        return count;
    }
};