611. 有效三角形的个数

611. 有效三角形的个数

此时$nums[l]+nums[mid]>nums[r]$，$l$取$[l,mid-1]$内任何一个数都满足条件，故有$ans+=(mid-l)$

我们现在的三元组（2，6，7）满足条件了，由于不等式右侧nums[r]固定，我们需要做的是调整不等式左侧的大小，尽可能让不等式满足

由于我们让$l$取$[l,mid-1]$内任何一个数就是尝试了让不等式左侧变得更大（依然满足条件），我们现在应该让不等式左侧变得更小，继续查看是否满足三角形条件，即向左移动mid，继续查找三元组

不满足条件时，两个小数字的和太小了，要让不等式左侧变大，只有一个选择：向右移动$l$取更大的数

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), less<int>());
        int n = nums.size();
        int ans = 0;
        // 每轮循环固定最大的数字不动
        for (int r = n - 1; r >= 2; r--){
            int l = 0;
            int mid = r - 1;
            while(l < mid){
                if(nums[l] + nums[mid] > nums[r]){
                    ans += (mid - l);
                    // mid是从r-1开始的，mid初始值较大，现在已经满足三角形条件，需要在较小数字中找满足三角形条件的数字
                    mid--;
                }else{
                    // 两个小数字的和太小了
                    l++;
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

那我们可以固定最小的值，用mid和r寻找三元组吗？

这种情况下，不满足三角形条件，两个小数字之和太小了，我们可以向右调整$mid$让$nums[l]+nums[mid]$的值更大，或向左调整$r$，让$nums[r]$的值更小，以满足三角形不等式。这操作起来就比较困难了：

我们向右调整mid，mid指向3，我们会漏掉（2，2，3）这个组合；向左调整r，r指向3，我们会漏掉（2，3，4）这个组合

所以我们应该把用于搜索三元组的两个指针放在不等式的同一侧，使得不满足三角形不等式时只有一个选择