尺取法：有效三角形的个数

桃扇骨 2023-10-06 23:02 13阅读 0赞

## 尺取法：有效三角形的个数 ##

#### 文章目录 ####

*  尺取法：有效三角形的个数
 *   *   *  问题：
         *  思路：
         *  代码：

#### 问题： ####

![在这里插入图片描述][072a22d591a241d7a8c16c3708a02bd0.png]

#### 思路： ####

该题需要使用三个元素的尺取法求解，三个元素的尺取法就是需要枚举一个，然后利用双指针扫描剩下的区间，其余两个元素分别为区间左端点与右端点，根据题中的不同条件移动这两个元素之一  
  我们先对题中数组进行排序，三条边长从小到大为 a、b、c，当且仅当 `a + b > c` 这三条边能组成三角形。这道题只能枚举最大边进行反向扫描，如果是枚举最短边正向扫描，若两边之和小于第三边，那么会有两种情况，一种是左指针往右移动，一种是右指针往左移动，移动的情况是不确定的。枚举最大边反向扫描时，如果两边之和小于第三边，只能是左指针往右，移动的情况是确定的，如果两边之和大于等于第三边，只能是右指针往左。  
  因此我们枚举数组最右边的最大值，下标k，剩下的区间中，区间右端点为第二大的值，下标为j = k - 1，最小值从下标i = 0开始，若nums\[i\] + nums\[j\] > nums\[k\]，那么i从当前的i开始，一直到j - 1，都能满足这个条件，因此我们找到了j - i个有效三角形，同时将右指针往左，j - -，寻找其他满足条件的情况。若nums\[i\] + nums\[j\] <= nums\[k\]，将左指针往右，i ++。在i >= j时，我们就遍历了区间中的所有情况。

#### 代码： ####

public int triangleNumber(int[] nums) {
        
            // write code here
            Arrays.sort(nums);
            int ans = 0;
            int i, j, k;
            for (k = nums.length - 1; k >= 2; k--) {
        
                j = k - 1;
                i = 0;
                while (i < j) {
        
                    if (nums[i] + nums[j] > nums[k]) {
        
                        ans += (j - i);
                        j--;
                    } else {
        
                        i++;   
                    }
                }
            }
            return ans;
        }

[072a22d591a241d7a8c16c3708a02bd0.png]: https://img-blog.csdnimg.cn/072a22d591a241d7a8c16c3708a02bd0.png