Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 26

Description

Valid Triangle Number

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:

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:

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

Constraints:

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

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int len = nums.size();
    int answer = 0;
    for(int i = 0; i < len - 2; i++) {
      for(int j = i + 1; j < len - 1; j++) {
        int l = nums[j] - nums[i];
        int h = nums[i] + nums[j];
        auto low = upper_bound(nums.begin() + j + 1, nums.end(), l);
        auto high = lower_bound(nums.begin() + j + 1, nums.end(), h);
        high -= 1;
        answer += high >= low ? high - low + 1 : 0;
      }
    }

    return answer;
  }
};

// Accepted
// 241/241 cases passed (294 ms)
// Your runtime beats 11.31 % of cpp submissions
// Your memory usage beats 8.77 % of cpp submissions (17.1 MB)