LeetCode611。有効な三角数
Leetcode611 Valid Triangle Number
配列が非負の整数で構成されている場合、あなたのタスクは、三角形の辺の長さとしてそれらをとると、三角形を作ることができる配列から選択されたトリプレットの数を数えることです。
例1：
Input: [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 注意：
The length of the given array won't exceed 1000. The integers in the given array are in the range of [0, 1000]. トピック ：配列を指定して、三角形に形成できるトリプルの数を決定します。
思想 ：参照 分析 。最初の三角形の条件は、任意の2つの辺の合計が3番目の辺よりも大きいことです。つまり、a+b>c、a+c>b with c+b>a判断には3つの条件があります。直接的な暴力サイクルTLE。配列nums並べ替え後、判定条件を1に減らすことができますa+b>c並べ替えのためc>b、c>a次に、不等式の左側に正の数を追加します条件を満たす。 use first、second 2つの短辺のシリアル番号を示します。third長辺が配置されているシリアル番号を示します。次にターゲットnums[third]この長辺、2つの短辺は左側にある必要があります（nums注文済み）firstシーケンス番号0から開始secondシリアル番号からthird-1最初は、これら2つの短辺が出会うまで常に調整できます。調整の原理はif nums[first] + nums[second] > nums[third]であり、この時点で固定されているため、三角形が見つかったことを示しますsecond位置とその後増加し続けますfirst上記の判断に満足する必要があります。このとき、対応する三角形の数はsecond - firstなので、secondの位置を更新します。
class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()) int len = nums.size() int cnt = 0 for(int third = len - 1 third >= 2 --third){ int first = 0 int second = third - 1 while(first < second){ if(nums[first] + nums[second] > nums[third]){ // such that first + second > third, there is no need to increment first cnt += (second - first) --second } else ++first } } return cnt } } と [LeetCode] 3Sum Smaller3つの数値の合計が小さい 。