力扣611. 有效三角形的个数（枚举，二分查找，对撞指针，NTT（正在想））

力扣611. 有效三角形的个数（枚举，二分查找，对撞指针，NTT（正在想）） 力扣611. 有效三角形的个数
题目描述：

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例：

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意：

数组长度不超过1000。
数组里整数的范围为 [0, 1000]。

思路一：暴力枚举。

class Solution {
public://先枚举最大数，再往下枚举次大数，保证不重复
void qsort(vector&a,int l,int r){
    int i=l,j=r,flag=a[l+(r-l)/2];
    do{
        while(a[i]flag)j--;
        if(i<=j)swap(a[i++],a[j--]);
    }while(i<=j);
    if(l& nums) {
    int jie=0;
    int n=nums.size();
    qsort(nums,0,n-1);
    for(int i=0;i=0;j--){
            for(int k=j-1;k>=0;k--)
               if(nums[i] 
时间复杂度为O（n^3）,快排也救不了它。（除非你改换编程语言）
 
 解法二：排序，加二分查找。 
class Solution {
public:
void qsort(vector&a,int l,int r){//快排模板之一
    int i=l,j=r,flag=a[l+(r-l)/2];
    do{
        while(a[i]flag)j--;
        if(i<=j)swap(a[i++],a[j--]);
    }while(i<=j);
    if(l& nums) {
    int n=nums.size();
    qsort(nums,0,n-1);
    int jie=0;
    for(int i=0;i 

 解法三：对撞指针，排序。 
解法四：NTT快速卷积（等我抓紧时间把它看懂） 
NTT快速卷积解法
 
（找时间完善ing，X﹏X，那个NTT快速卷积太秒了）
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5592871.html