LeetCode_双指针_中等_611.有效三角形的个数

1.题目

给定一个包含非负整数的数组 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-triangle-number

2.思路

（1）排序 & 暴力穷举法
排序 & 暴力穷举法比较容易想到，具体步骤如下：
① 先将数组 nums 进行升序排序；
② 使用 3 层 for 循环来枚举每一个三元组 (nums[i], nums[j], nums[k])，其中，nums[i] ≤ nums[j] ≤ nums[k]，所以如果 nums[i] + nums[j] > nums[k]，那么该三元组一定可以构成三角形；否则就构不成，需要注意的是，这里存在一个过滤操作，即如果 nums[k] ≥ nums[i] + nums[j]，由于数组 nums 已经是按升序排好的，所以后面的 nums[k] 肯定也 ≥ nums[i] + nums[j]，所以此时可以结束第 3 层循环；
③ 在穷举的过程中，使用变量 res 来记录组成三角形三条边的三元组个数，穷举结束后直接返回 res 即可。

（2）排序 & 双指针
思路参考本题官方题解。

① 先将数组 nums 进行升序排序；
② 使用 1 层 for 循环来枚举 i，当 i 固定时，维护双指针 left 和 right；
③ 再使用 1 层 for 循环来枚举 left，每次将 left 向右移动一个位置时，尝试不断地向右移动 right，使得 right 是最大的满足 nums[right] < nums[i] + nums[left] 的下标，然后再用 res += Math.max(right - left, 0) 来累加答案。
④ 当枚举结束后，直接返回 res 即可。

3.代码实现（Java）

//思路1————排序 & 暴力穷举法
class Solution {
    public int triangleNumber(int[] nums) {
        int res = 0;
        int length = nums.length;
        //将数组 nums 进行升序排序
        Arrays.sort(nums);
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                for (int k = j + 1; k < length; k++) {
                    if (nums[i] + nums[j] > nums[k]) {
                        res++;
                    } else {
                        //由于数组 nums 已经是按升序排好的，所以后面的 nums[k] 肯定也大于等于 nums[i] + nums[j]
                        break;
                    }
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//思路2————排序 & 双指针
class Solution {
    public int triangleNumber(int[] nums) {
        int res = 0;
        int length = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < length; i++) {
            int right = i;
            for (int left = i + 1; left < length; left++) {
                while (right + 1 < length && nums[right + 1] < nums[i] + nums[left]) {
                    right++;
                }
                res += Math.max(right - left, 0);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18