零、写在前面

英雄哪里出来《算法零基础100讲》传送门

https://bbs.csdn.net/forums/hero?category=0&typeId=17913https://bbs.csdn.net/forums/hero?category=0&typeId=17913

本题知识回顾

本章主要描述了如何实现选择排序

《算法零基础100讲》(第34讲) 排序入门 - 选择排序_英雄哪里出来-CSDN博客排序入门 之 选择排序https://blog.csdn.net/WhereIsHeroFrom/article/details/121484862每天会开启一篇试读文章，每日坚持打卡就可以一直白嫖哦

一、题目

611. 有效三角形的个数

难度中等321

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

示例 1:

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

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

力扣https://leetcode-cn.com/problems/valid-triangle-number/

二、解题

思路：1.对数据进行排序      2.两层循环枚举两条边，  3.通过a+b>c确定第三边，用二分查找的方法   4.返回结果

贴一个二分查找的知识点链接

❤️《画解数据结构》九张动图，画解顺序表❤️_英雄哪里出来-CSDN博客

void Swap(int*a,int*b){  //实现两个变量中存储的数的的交换
    int tmp=*a;  //中间变量
    *a=*b;  //交换
    *b=tmp;//交换
}
  
void SelectionSort(int n,int*a){   //实现数据从小到大的排序，即本章所讲述的内容
    int i,j;
    for(i=0;i<n-1;i++){
        int min=i;            //就是从头开始找最小的，和a[0]交换，然后找第二小的，和a[1]
        for(j=i+1;j<n;j++){    //交换，以此类推
            if(a[j]<a[min]){
                min=j;
            }
        }
    Swap(&a[i],&a[min]); //调用上边的交换函数
    }
}
int triangleNumber(int* nums, int numsSize){
    SelectionSort(numsSize,nums);
    int ans=0;
    for(int i=0;i<numsSize;i++){   //一层循环确定一条边
        int j=i+1;
        for(j;j<numsSize;j++){   //2层循环再确定一条边
            int left=j+1,right=numsSize-1,k=j;
            while(left<=right){    //这里通过二分查找，确定第三边的大小，以为排过序，所以
                int mid=(right+left)>>1;//从边2，到边3之间的数都可以作为边3的值
                if(nums[mid]<nums[i]+nums[j]){
                    k=mid;
                    left=mid+1;
                }
                else{
                    right=mid-1;
                }
            }
            ans+=k-j;   //这就是结果，然后继续循环，重新确定边1边2。

        }
    }
    return ans;   //返回结果
}

三、结果