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

文章目录

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

问题：

思路：

该题需要使用三个元素的尺取法求解，三个元素的尺取法就是需要枚举一个，然后利用双指针扫描剩下的区间，其余两个元素分别为区间左端点与右端点，根据题中的不同条件移动这两个元素之一
我们先对题中数组进行排序，三条边长从小到大为 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;
    }