package LeetCode.triangleNumber;

import java.util.Arrays;

/**
 * @author Soap
 * time 2021年8月5日 3:00 上午
 * 611. 有效三角形的个数
 */
public class triangleNumberDemo {
 public static void main(String[] args) {
 Solution s = new Solution();
 System.out.println(s.triangleNumber(new int[]{2, 2, 3, 4}));
 }
}

class Solution {
 public int triangleNumber(int[] nums) {
 int res = 0;
 int n = nums.length;

 Arrays.sort(nums);

 for (int i = 0; i < n; ++i) {
 for (int j = i + 1; j < n; ++j) {

 int l = j + 1, r = n - 1;
 int mid = l + (r - l) / 2;

 while (l <= r) {
 if (nums[mid] < nums[i] + nums[j]) { //第三边小于两边之和,符合;
 l = mid + 1;
 } else {
 r = mid - 1;
 }
 mid = l + (r - l) / 2;
 }
 if (nums[r] + nums[j] > nums[i])
 res += r - j;
 System.out.println();
 System.out.println("i = " + i);
 System.out.println("j = " + j);
 System.out.println("r = " + r);
 System.out.println("res = " + res);
 }
 }
 return res;
 }
}