【算法专题突破】双指针 - 有效三角形的个数（5）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法专题突破】双指针 - 有效三角形的个数（5）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

1. 题目解析

题目链接：611. 有效三角形的个数 - 力扣（Leetcode）

【算法专题突破】双指针 - 有效三角形的个数（5）,算法专题训练,算法,c++

我们可以根据示例1来理解这一道题目，

他说数组里面的数可以组成三角形三条边的个数，

那我们先自己枚举一下所有情况看看：

【2， 2， 3】

【2， 2， 4】

【2， 3， 4】

总共是四种情况，

而第二种情况是不成立的，看看示例，我们可以知道，虽然都是2，

但是不同位置可以看成不同的元素。

2. 算法原理

一开始我们看到这样的题目，实际上第一个想到的解法就是暴力枚举，

把所有情况枚举一遍然后判断，但是这是一个O(N3)的解法，

我们可以通过单调性和双指针的方式来优化我们的时间复杂度，

具体思路如下：

1. 通过sort 找到最大值

2. 使用双指针快速求出符合题目要求的数

具体操作如下：

以这个排好序的数组为例：

【算法专题突破】双指针 - 有效三角形的个数（5）,算法专题训练,算法,c++

左指针指向最小的元素，右指针指向最大元素的左边元素，

跟据三角形两边之和需要大于第三边的性质，

【算法专题突破】双指针 - 有效三角形的个数（5）,算法专题训练,算法,c++

如果 2 + 9 > 10，就证明 3 + 9，4 + 9 等等情况都会大于10，

这样我们就直接计算出 right - left 种适合的情况，

这样就能让所有的数都跟 9 结合过了，就让 right--。

【算法专题突破】双指针 - 有效三角形的个数（5）,算法专题训练,算法,c++

如果 2 + 5 <= 10，就证明无论是 2 + 4 还是 2 + 3 等等情况，都会<=10，

所以我们就能直接让 left++，去找更大的数。

最后等left 和 right 相撞，就能求出所有适合的情况了。

3. 代码编写

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        for(int i = nums.size() - 1; i > 1; i--) {
            int left = 0, right = i - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    ans += (right - left);
                    right--;
                }
                else left++;
            }
        }
        return ans;
    }
};