算法双指针系列--Day4-有效三角形的个数

---

前言

本题采用排序+对撞指针解决,下面是对撞指针的简介
结尾会附上C++与Java的完整代码

对撞指针：一般用于顺序结构中，也称左右指针。
• 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
◦ left == right （两个指针指向同一个位置）
◦ left > right （两个指针错开）

一、题目链接

有效三角形的个数

二、题目描述

三、补充知识

1.C++中的sort函数是专门用来排序的，可以用来排数组，也可以用来排vector这种容器。对于容器来说调用sort函数需要传迭代器就是nums.begin()和nums.end()。不熟悉的小伙伴可以把这俩理解成数组下标，一个指向数组第一个元素一个指向数组最后一个元素。调用sort函数就是告诉他数组的起始点和终止点，让它排序就好了，默认是从小到大排序的。
2.int n = nums.size()就是把数组名叫nums的一个数组它里面有几个元素赋值给n，比如数组里有四个元素那n就是4.

四、解法一（暴力求解会超时）

我们首先想到的当然是暴力解法了，管他三七二十一，直接三层for循环每个都遍历一遍，看能不能构成三角形。判断条件肯定是两边之和大于第三边，两边之查小于第三边了.
虽然是暴力解法，但我们也不至于暴力到底，可以优化一下。
判断三⻆形的优化：
▪ 如果能构成三角形，需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。
证明:
假设a<b<c,如果a+b>c那么由a<b<c、a+b>c可得：b+c>a、a+c>b、a>c-b、b>c-a、c>b-a。满足任意两边之和大于第三边，两边之差小于第三边。
▪ 因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三角形。
代码：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1. 排序
        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 0;
        // 2. 从⼩到⼤枚举所有的三元组
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // 当最⼩的两个边之和⼤于第三边的时候，统计答案
                    if (nums[i] + nums[j] > nums[k])
                        ret++;
                }
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

果不其然被制裁了:

五、解法二(排序+双指针)

借用上面的优化思想即
判断三⻆形的优化：
▪ 如果能构成三角形，需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。
▪ 因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三角形。
在从小到大排好序后，我们可以设立双指针来解决问题。（双指针未必一定是指针，它只是一个名字而已，在这里的指针即为数组下标）
设最长边枚举到 i 位置，区间 [left, right] 是 i 位置左边的区间（也就是比它小的区间）：

◦ 如果 nums[left] + nums[right] > nums[i] ：

▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[i] 大的二元组
▪ 满足条件的有 right - left 种，如上图所示2下标为0，3下标为2，2-0=2，那么就有两个三角形满足条件分别是2，3，4和2，3，4注意这里2的来源不同，所以算两个三角形而不是一个。
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进入下⼀轮判断
◦ 如果 nums[left] + nums[right] <= nums[i] ：

▪ 说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件
的⼆元组
▪ left 位置的元素可以舍去， left++ 进入下轮循环

六、代码编写

C++完整代码：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1. 优化
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int ret = 0, n = nums.size();
        for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数
        {
            // 利⽤双指针快速统计符合要求的三元组的个数
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：

Java完整代码：

class Solution {
    public int triangleNumber(int[] nums) {
        // 1. 优化：排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int ret = 0, n = nums.length;
        for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数
        {
            // 利⽤双指针快速统计出符合要求的三元组的个数
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果：