思路
暴力
代码
二分搜索
算法
双指针

leetcode 611. 有效三角形的个数

August 04, 2021

思路

暴力

数学公式: a, b, c 三条边满足可组成三角形的条件为

  • a + b > c
  • a + c > b
  • b + c > a

当 a, b, c 三者有序,也就是 a < b < c 场景下, 只满足 a + b < c 即可, 因此,可以很自然的想到三重循环的遍历算法

代码

var triangleNumber = function (nums) {
  nums.sort((a, b) => a - b);

  let count = 0;

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] > nums[k]) {
          count++;
        }
      }
    }
  }

  return count;
};
  • 时间复杂度: $O(N ^ 3)$
  • 空间复杂度: $O(1)$

二分搜索

注意到三重循环中,最内部循环只需要找到第一个 k, 使得 nums[i] + nums[j] <= nums[k], 那么当前k之前的所有 k1 都满足 nums[i] + nums[j] > nums[k], 又原数组是有序的,可以通过二分查找将最内层的时间开销从 O(N) 优化到 O(logN)

算法

var triangleNumber = function (nums) {
  nums.sort((a, b) => a - b);

  let count = 0;

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      const k = find(nums, j + 1, nums.length - 1, nums[i] + nums[j]);
      count += k - j - 1;
    }
  }

  return count;
};

// 找到第一个K, 使得nums[k] >= target
function find(nums, start, end, target) {
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (nums[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return start;
}
  • 时间复杂度: $O(N * N * logN)$
  • 空间复杂度: $O(1)$

双指针


feiker 少年起而行之