题目链接

LeetCode

题目描述

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

  • 1 <= nums.length <= 1000

  • 0 <= nums[i] <= 1000

    解题思路

    方法一：双指针

    对于正整数 a, b, c 它们可以作为三角形的三条边，当且仅当：
    image.png
    均成立。如果我们将三条边进行升序排序，使它们满足a≤b≤c，那么 a + c > b 和 b + c > a 使一定成立的，我们只需要保证 a + b > c。
    因此，我们可以将数组 nums 进行升序排序，然后双指针遍历结果。

    1. class Solution {
    2.   public int triangleNumber(int[] nums) {
    3.       int n = nums.length;
    4.       Arrays.sort(nums);
    5.       int res = 0;
    6.       // i 是 a 的下标
    7.       for(int i = 0; i < n; ++i){
    8.           if(nums[i] == 0){
    9.               continue;
    10.           }
    11.           // j 是 b 的下标
    12.           for(int j = i + 1; j < n; ++j){
    13.               int k = j + 1; // k 是 c 的下标
    14.               // 遍历c的下标，左边的都是成立的
    15.               while(k < n && nums[j] + nums[i] > nums[k]){
    16.                   ++k;
    17.               }
    18.               res += Math.max(0, k - j - 1);
    19.           }
    20.       }
    21.       return res;
    22.   }
    23. }

  • 时间复杂度 O(n^2)

  • 空间复杂度 O(log n)