有效三角形

• 原来没有逻辑的代码

class Solution { public: int triangleNumber(vector<int>& nums)
 { int s = nums.size(); 
 if(s<3)
 { return 0; } 
 int count=0; 
 int m=0,n=0; 
 ranges::sort(nums); 
 for(int i=s-3;i>1;i--)
 { 
 int x = nums[i]; 
 m=0; 
 n=i-1; 
 while(m<n)
 { 
 if(nums[m]+nums[n]>x)
 {
  count++;
  //呜呜 错误的逻辑！
   for(n--;n>m&&nums[n]==nums[n+1];n--)
   count++; 
   for(m++;m<n&&nums[m]==nums[m-1];m++)count++; 
   } 
   else{ m++; }
    }
     }
      return count; 
      } 
      };
 

• • 然后使用两个指针left和right，left从0开始，right从i-1开始，向中间移动，检查nums[left] + nums[right] > nums[i]。如果成立，那么所有在left和right之间的元素与right组合都能满足条件，所以==count += right - left==，然后right—。否则，left++。

• class Solution {

public:

int triangleNumber(vector& nums) {

int s = nums.size();

if(s<3){

return 0;

}

int count=0;

int m=0,n=0;

ranges::sort(nums);

for(int i=s-1;i>1;i—){

int x = nums[i];

m=0;

n=i-1;

while(m<n){

if(nums[m]+nums[n]>x){

count+=n-m;

n—;

}

else{

m++;

}

}

}

return count;

}

};