611. Valid Triangle Number

• 611. Valid Triangle Number
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

Pitfall

容易写成O(N^2 * LogN)的，直接apply 3sum，只需要从尾开始不断选择一个数，每次符合两小边之和大于第三边即可

public int triangleNumber(int[] nums) {
    if (nums == null || nums.length <= 2) {
      return 0;
    }
    final int n = nums.length;
    Arrays.sort(nums);
    int count = 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]) {
          count += r - l;
          r--;
        } else {
          ++l;
        }
      }
    }
    return count;
  }



Solution

Solution