代码训练营+剑指Offer

题目编号

题目思路和细节

二分法：函数传入vector返回target（查找目标的数组下标）或-1（未查到目标）。
使用二分法的前提条件：有序数组，同时数组中无重复元素（一旦有重复元素，使用二分查找返回的元素下标可能不是唯一的）。
步骤：
- 定义数组下标：left、right和middle。
- while循环查找，循环内if分支裁剪。
- return。
注意事项：
- 对搜索区间定义明确，要么左闭右闭，要么左闭右开。此为不变量，对应两种写法。
- middle赋值时注意，int型变量相加有越界风险。防止溢出可以进行如下操作：
```
  int middle = left + ((right - left) >> 1);
```
易错点：
- while循环条件是否符合对区间的定义（left是否可以等于right）？如果符合就要进行查找。
- 使用if进行区间裁剪时，注意裁剪后的区间要和定义相吻合。

描述：函数传入vector和一个给定int值val，原地移除（不能使用额外的数组空间）所有数值等于val的元素，并返回移除后数组的新长度。
目的：实现vector中erase函数的删除功能。
数组理论：删除元素只能覆盖，内存空间大小不变。C++中，vector内设有计数器，调用erase后（$O(n)$操作，删除一个元素要整体前移进行覆盖）就会自动减1，所以返回的长度是size-1。
暴力解法：双层for循环。第一层遍历到目标数值时，加入第二层来进行覆盖。时间复杂度为$O(n^2)$。
双指针法：用一层for循环完成。定义快慢指针，for循环完成快指针的移动。
- 快指针：获取删除后新数组所需要的元素，筛掉val。
- 慢指针：获取新数组元素更新后的下标值。将快指针寻找到的值赋给慢指针所在的位置。