611. Valid Triangle Number

Posted on Edited on In

611. Valid Triangle Number

Description

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

1
2
3
4
5
6
Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

1
2
Input: nums = [4,2,3,4]
Output: 4

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Hints/Notes

Solution

Language: C++

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
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // triangle: a + b > c
        ranges::sort(nums);
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            // if (i && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.size(); j++) {
                // if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                // now we need to find the max index with nums[k] < nums[i] + nums[j]
                // range of k: [j + 1, num.size() - 1]
                int left = j, right = nums.size(), target = nums[i] + nums[j];
                while (left + 1 < right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] >= target) {
                        right = mid;
                    } else {
                        left = mid;
                    }
                }
                // so all right has value >= target, right can be at j + 1
                res += right - j - 1;
            }
        }
        return res;
    }
};