611. Valid Triangle Number

, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int triangleNumber(int[] nums) {
        int count = 0;

        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                int target = nums[i] + nums[j];

                // 在 [j + 1, nums.length - 1] 中寻找小于 target 的元素个数
                int left = j + 1, right = nums.length - 1;
                while (left <= right) {
                    int mid = (left + right) >>> 1;
                    if (nums[mid] < target) {
                        left = mid + 1;
                    } else if (nums[mid] > target) {
                        right = mid - 1;
                    } else {
                        right = mid - 1;
                    }
                }

                // now: right, left
                count += left - j - 1;
            }
        }

        return count;
    }
}

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);

        int count = 0;
        for (int k = nums.length - 1; k >= 2; k--) {
            int i = 0, j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    // nums[i], nums[i + 1] ... nums[j - 1] 这部分数字加上 nums[j] 都满足条件
                    count += j - i;
                    j--; // 固定 nums[j] 的组合已经统计完毕 
                } else {
                    // 此时和小于等于 nums[k], 只能增加最小边的值
                    i++;
                }
            }
        }

        return count;
    }
}

References

611. Valid Triangle Number