Valid Triangle Number

Description

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

Solution(javascript)

// BinarySearch O(n^2(logn))
// 两轮遍历确定两条边，BS 查找第三条边的范围
// const triangleNumber = (nums = []) => {
//   const binarySearch = (start, target) => {
//     let left = start
//     let right = nums.length - 1
//     while (left <= right) {
//       const middle = Math.floor((left + right) / 2)
//       if (nums[middle] >= target) {
//         right = middle - 1
//       } else {
//         left = middle + 1
//       }
//     }
//     return right
//   }
//   let count = 0
//   nums.sort((a, b) => a - b)
//   for (let i = 0; i < nums.length - 2; i++) {
//     for (let j = i + 1; j < nums.length - 1; j++) {
//       const k = binarySearch(j + 1, nums[i] + nums[j])
//       if (k !== null && k > j) {
//         count += k - j
//       }
//     }
//   }
//   return count
// }

// O(n^2)
// 还是两轮遍历确定两条边，当三条边不满足条件时，往右走
const triangleNumber = (nums = []) => {
  nums.sort((a, b) => a - b)
  let k = 2
  let count = 0
  for (let i = 0; i < nums.length - 2; i++) {
    for (let j = i + 1; j < nums.length - 1; j++) {
      k = j + 1
      while (nums[k] < nums[i] + nums[j]) {
        k += 1
      }
      count += k - j - 1
    }
  }
  return count
}