Question

611. Valid Triangle Number

中文文档

Description

Given an integer array nums, return _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: nums = [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

Example 2:

Input: nums = [4,2,3,4]
Output: 4

 

Constraints:

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

Solutions

Solution 1

class Solution:
  def triangleNumber(self, nums: List[int]) -> int:
    nums.sort()
    ans, n = 0, len(nums)
    for i in range(n - 2):
      for j in range(i + 1, n - 1):
        k = bisect_left(nums, nums[i] + nums[j], lo=j + 1) - 1
        ans += k - j
    return ans

class Solution {
  public int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int res = 0;
    for (int i = n - 1; i >= 2; --i) {
      int l = 0, r = i - 1;
      while (l < r) {
        if (nums[l] + nums[r] > nums[i]) {
          res += r - l;
          --r;
        } else {
          ++l;
        }
      }
    }
    return res;
  }
}

class Solution {
public:
  int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int ans = 0, n = nums.size();
    for (int i = 0; i < n - 2; ++i) {
      for (int j = i + 1; j < n - 1; ++j) {
        int k = lower_bound(nums.begin() + j + 1, nums.end(), nums[i] + nums[j]) - nums.begin() - 1;
        ans += k - j;
      }
    }
    return ans;
  }
};

func triangleNumber(nums []int) int {
  sort.Ints(nums)
  ans := 0
  for i, n := 0, len(nums); i < n-2; i++ {
    for j := i + 1; j < n-1; j++ {
      left, right := j+1, n
      for left < right {
        mid := (left + right) >> 1
        if nums[mid] >= nums[i]+nums[j] {
          right = mid
        } else {
          left = mid + 1
        }
      }
      ans += left - j - 1
    }
  }
  return ans
}

function triangleNumber(nums: number[]): number {
  nums.sort((a, b) => a - b);
  let n = nums.length;
  let ans = 0;
  for (let i = n - 1; i >= 2; i--) {
    let left = 0,
      right = i - 1;
    while (left < right) {
      if (nums[left] + nums[right] > nums[i]) {
        ans += right - left;
        right--;
      } else {
        left++;
      }
    }
  }
  return ans;
}

impl Solution {
  pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    let n = nums.len();
    let mut res = 0;
    for i in (2..n).rev() {
      let mut left = 0;
      let mut right = i - 1;
      while left < right {
        if nums[left] + nums[right] > nums[i] {
          res += right - left;
          right -= 1;
        } else {
          left += 1;
        }
      }
    }
    res as i32
  }
}

Solution 2

class Solution {
  public int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int ans = 0;
    for (int i = 0, n = nums.length; i < n - 2; ++i) {
      for (int j = i + 1; j < n - 1; ++j) {
        int left = j + 1, right = n;
        while (left < right) {
          int mid = (left + right) >> 1;
          if (nums[mid] >= nums[i] + nums[j]) {
            right = mid;
          } else {
            left = mid + 1;
          }
        }
        ans += left - j - 1;
      }
    }
    return ans;
  }
}