1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] <= nums[i]) {
                    left += 1;
                } else {
                    ans += right - left;
                    right -= 1;
                }
            }
        }
        return ans;
    }
}

构造三角形就是两边之和大于第三边.
我的想法就是先sort一下. 然后模仿3sum那样用两个pointer. 但是我是从左到右遍历. 因此比如第0个元素为一边, 从1到n - 1的元素开始two pointers遍历. 如果nums[i] + nums[left] > nums[right], 这就说明left到right间的元素和nums[i]配对都会大于nums[right], 此时我们可以在ans中加上. 但是如果nums[i] + nums[left] <= nums[right], 可能有些元素在right左侧能和i, left构成三角形. 于是我们要不移动left, 移动right, 到某个位置后, 我们发现可以于是在ans中添加个数. 此时我们就要让left再 + 1. 但这里的问题就是, right也要重置到最右端, 因为在此时right右侧可能有的元素可以和现在的nums[i], nums[left]组成三角形了, 毕竟left左移了.

因此这样做的问题就是一旦left左移, right就要重置到最右端.

但是网友就是牛逼, 我们倒着遍历即可. 也就是我们先确定最大边是多少. 然后维护两个pointers, 左一个, 右一个. 如果nums[left] + nums[right] <= nums[big]. 我们需要移动left. 如果nums[left] + nums[right] > nums[big], 这说明从right到left间的数字都可以和right配对大于big, 此时ans加上这些对儿即可. 此时我们知道right作为第二大边的情况没有了. 我们移动right. 那此时需要移动left吗? 答案是不需要, 因为此时最左边到left这里和right配对都小于big, 更何况此时right还移动了一格. 因此我们知道right更新后, left左侧的位置都不满足, 至于left满不满足不一定了, 我们当然也没有移动left.

等于思路是先确定一个big, 再确定一个second big. 然后left就移动, 移动到某个位置满足题意, 把答案加到ans上, 移动second big一位, 然后继续移动left, 判断..这个过程.

时间复杂度: O(n^2)
空间复杂度: O(1)