二分

左闭右闭

target定义在[left, right]区间：

  • while(left <= right) 要使用<=，因为left == right是有意义的

  • if(nums[mid] > target) right要赋值为mid-1，因为这个nums[mid]一定不是target

    左闭右开

    target定义在[left, right)区间

  • while(left < right) 要使用<，因为left == right是没有意义的

  • if(nums[mid] > target right被更新为mid，因为维护的是一个左闭右开的区间

    lower_bound() && upper_bound()

    lower_bound()求出第一个大于等于target的下标，upper_bound()求出第一个大于target的下标 ```

    include

    include

    include

    using namespace std;

bool cmp(int a, int b){return a<=b;} int main(){ vector v; v.push_back(1); v.push_back(3); v.push_back(2); v.push_back(3); v.push_back(4);

  1. sort(v.begin(), v.end(),cmp);
  2. int l = lower_bound(v.begin(), v.end(), 3) - v.begin();
  3. int r = upper_bound(v.begin(), v.end(), 3) - v.begin();
  5. for(int i = 0;i < v.size();i++) {
  6.     cout<<v[i]<<' ';
  7. }// 1 2 3 3 4
  8. cout<<endl<<l<<' '<<r<<endl;//2 4

}

  1. <a name="PCS0L"></a>
  2. # 移动数组-快慢指针
  3. fast指向原数组的遍历下标，slow指向新数组的遍历下标，只不过新旧数组都用的是同一块内存，也就是同一个vector

int removeElement(vector& nums, int val) { int slow = 0; for(int fast = 0; fast < nums.size(); fast++) { if(nums[fast] != val) { nums[slow++] = nums[fast]; } } return slow; }

  1. <a name="chMAf"></a>
  2. # 尺取法（滑动窗口）
  3. 问题：求整数数组里，总和小于给定值的最小长度区间。<br />分析：固然可以求出前缀和，然后枚举起点二分查找。但还有一种O(n)的解法<br />输入样例：a = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8], target = 15<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/211799/1632975791626-db624054-80c0-49b0-95a2-f8d654cc3621.png#height=452&id=Rj64f&margin=%5Bobject%20Object%5D&name=image.png&originHeight=904&originWidth=968&originalType=binary&ratio=1&size=990122&status=done&style=none&width=484)

class Solution { public: int minSubArrayLen(int target, vector& nums) { if(nums.size() == 0) return 0; vector sum; sum.push_back(0); for(int i=0;i<nums.size();i++) { sum.push_back(nums[i]+sum.back()); } int l=1,r=1,res=0x7fffffff; for(;l<=r && r<=nums.size();) { if(sum[r]-sum[l-1]<target) r++; else { res = min(res,r-l+1); l++; } } return res==0x7fffffff?0:res; } }; ```

image.png

成环

分为考虑首元素不考虑尾元素、考虑尾元素不考虑首元素、不考虑首元素和尾元素三种情况

排序

image.png