双指针算法： 有效三角形的个数

🎈个人主页:🎈 :???初阶牛???
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一

前言

声明：题目来源于： 力扣

一、有效三角形个数

题目链接：传送门

(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

(2)解题思路

如果我们能找到三条边中，较短的两条边之和大于第三边（最长的边），则这是那边就可以构成一个三角形。

1. 为了保证找到两个较小边与最长边的关系，我们需要将数据先排序。
   c从倒数第一个位置开始，b为c的前一个位置，a为最开始的位置。
   

2. 先固定c：
   让a往前移动（相当于再固定b），知道a+b>c时停止
   
   也就表示7到13之间，所有的数与15搭配，都符合要求，个数为b-a

3. 将b向前（左）移动，继续步骤2
   

4. 当a>b,表明c为最后一个位置时，所有可能已经全部计算了，此时将c向前（左）移动一步，重复步骤2.

(3)代码展示:

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int a = 0, b = nums.size() - 2, c = nums.size() - 1;
        sort(nums.begin(), nums.end());
        int count = 0;
        while (c >= 2) {

            while (a < b) {
                //先固定c，在前面的序列中找到两个边之和大于c
                if (nums[a] + nums[b] <= nums[c]) {
                    a++;
                }
                else {
                    //此时代表a到b之间都是符合条件的（因为升序）
                    count += (b - a);
                    b--;
                }   
            }
            //c开始往前移动一步，下次循环依旧相当于固定
            c--;
            //更新a和b
            a = 0;
            b = c - 1;
           
        }
        return count;
    }
};