二分查找和双指针（滑动窗口）

日期: 2025年9月27日

今天的leetcode题，是统计可以成为三角形的三元组，核心是两个短边之和大于第三边，方法是枚举短边，维护长边。

方法一：排序+二分查找

主要是二分查找：

while(left<=right){     //终止条件是left>right
    int mid=left+(right-left)/2;
    if(nums[mid]>=target){
        k=mid;
        right=mid-1;
    }
    else{
        left=mid+1;
    }
} 

1. 注意每次更新边界指针，都是mid+1 or mid-1. 不是mid,这样才可能达到停止条件；
2. 如果二分查找只是为了查找，直接返回是可以的，当循环退出，就是查不到；但是二分不止用于查找，还可能是大于某数的下/上界，同时要考虑有重复的，不是只要得到了目标数，减1或加1就能拿到上界or 下界，以本题为例，我们要的是下界，即要：第一个大于等于target的数的下标，那么该下标减去起始查找的下标再减1（要考虑题目具体情况），那么我就维护这个下界，每次，right还能左移，就以当前right为下界。 假如题目要的是上界，即求最后一个小于等于target的数，那就每次left能右移（mid角标对应的值小于等于target），就更新.

这个思想可以提炼为：要什么东西，就维护什么 本题Deepseek还给出一个细节，直接从j+1开始搜，不用再考虑前面的；

总结

1. 二分查找的停止条件是：left>right;即while(left≤right)
2. 注意每次更新左右指针是：mid+1 or mid-1
3. 要一个大于等于或小于等于目标值的上、下界，就是若right/left 可以继续左/右移时，更新维护k值。

方法2：排序+双指针

问题可以重述为：在有序数组中，固定i,k,求最大$k(i,j)$的满足nums[k]<nums[i]+nums[j]

也就是说，固定i,当j增大时，最大的k也会继续增大，那么我用两个指针分别指示j,k的位置；好处是：j，k指针只会向右移，那么j右移一次，就继续尝试移动k,来看是否能满足条件

for(int i=0;i<len;i++){
    int k=i+1; //初始化k
    for(int j=i+1;j<len;j++){
        while(k + 1 < n &&nums[k+1]<nums[i]+nums[j]) //尝试增加k
            ++k;
        res+=max(k-j,0); //细节，可能找不到k,那就保证不出现负数
    }
}