有效三角形的个数 ---- 双指针

题目链接

题目:

分析:

• 这道题的意思就是将数组的元素, 拿出三个数, 能构成三角形就是有效的
• 判断是否能构成三角形的条件: 两边之和大于第三边, 我们只需找到三个数中最小的两个数之和是否大于第三边, 大于则可以构成三角形
• 解法一: 暴力解法, 即找到所有的三元组, 并挨个判断, 但效率低时间复杂度高
• 解法二:
  • 为了更快的找到三元组, 我们可以先对数组进行排序
  • 我们先假设最大的数为第三边c, 两边中的一边是最小的数a,  一边是除了最大数c的最大数b
  • 如果a+b>c, 能构成三角形, 此时, a和b中间的数都比a大, 那么这些数加上b, 一定也是>c的, 那么a+b再小一点是否可以呢? 即 将b减小1, 即向左移动1, 再次判断
  • 如果a+b<=c, 不能构成三角形, 那么a+b再大一点是否可以呢? 即将a增加1, 即向右移动1, 再次判断
  • 直到ab相遇, 说明与最大值c的组合已全部找完了, 下面要找第二大的数字的组合, 即c向左移动1, 再次循环找ab
• 总结:想要最大最小数, 或进行运算时, 考虑先对数组排序, 再使用左右指针按需计算

思想:

1. 先对数组进行排序
2. 定义一个n记录有效三角形的个数
3. 定义c 指向最大的数, left为最左边, right为c的左边一个
4. c从最后不断向前, 循环判断left+right 和c 的大小, 直到left和right相遇
   1. 如果left+right > c, n+=right-left, right--
   2. 如果left+right < c, left++

 代码:

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = 0;
        int c = nums.length - 1;
        while (c >= 2) {
            int left = 0;
            int right = c - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[c]) {
                    n += (right - left);
                    right--;
                } else {
                    left++;
                }
            }
            c--;
        }
        return n;
 
    }
}