611. 有效三角形的个数

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
class Solution {
    public int triangleNumber(int[] nums) {
        int ans = 0;
        // 先排序
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                // 只需要a+b>c即可
                int a = nums[i];
                int b = nums[j];
                // 二分查找j+1~n-1的范围内符合条件的数据,使用二分查找
                int l = j+1;
                int r = n-1;
                int k = j;
                while (l <= r){
                    int mid = (l+r)/2;
                    if ((a+b) > nums[mid]){
                        l = mid + 1;
                        k = mid;
                    }else{
                        r = mid - 1;
                    }
                }
                ans += k - j;
            }
        }
        return ans;
    }
}