在返回结果时，有可能不等于target注意判断是返回>=，还是<=的结果。
704.二分查找
34.在排序数组中查找元素的第一个和最后一个位置
69.x 的平方根
704.二分查找
二分查找主要用于有序数组，且无重复元素
边界问题：
左闭右闭：
left可以等于right， 此时循环的条件为left <= right;
判断当mid 不等于target时，此时left = mid + 1或者right = mid-1;
左闭右开：
left不能等于right， 此时循环的条件为left < right;
判断当mid 不等于target时，此时left = mid + 1或者right = mid;
左闭右开写法：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(left < right){
int mid = (right - left) / 2 + left; //防止（left+rigt）溢出
if(nums[mid] < target){
left = mid+1;
}else if(nums[mid] > target){
right = mid;
}else{
return mid;
}
}
return -1;
}
}
69.x 的平方根
用二分法求平方根且要求只取整数， a 2 < = x a^2 <= x a2<=x，所以用二分时，如果最后跳出循环后应该取小的一个；
class Solution {
public int mySqrt(long x) {
long left = 0;
long right = x;
while(left <= right){
long mid = (right - left)/2 + left;
long temp = mid * mid;
if(temp < x){
left = mid + 1;
}else if(temp > x){
right = mid - 1;
}else{
return (int)mid;
}
}
return left;
}
}
其他：可以用牛顿迭代法，二次收敛，比二分查找更快
快慢指针：27.移除元素
844.比较含退格的字符串
快指针遍历数组，慢指针填补相应的元素。
- 移除元素
class Solution {
public int removeElement(int[] nums, int val) {
// 快慢指针
int fastIndex = 0;
int slowIndex;
for (slowIndex = 0; fastIndex < nums.length; fastIndex++) {
if (nums[fastIndex] != val) {
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex;
}
}
844.比较含退格的字符串
方法一、由于先进后出的特征，考虑用栈；这里用StringBuffer代替stack更方便。
class Solution {
public boolean backspaceCompare(String s, String t) {
String a = build(s);
String b = build(t);
return a.equals(b);
}
public String build(String s){
StringBuffer s1 = new StringBuffer("");
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '#' && s1.length() > 0){
s1.delete(s1.length()-1, s1.length());
}else if(s.charAt(i) != '#'){
s1.append(s.charAt(i));
}
}
return s1.toString();
}
}
方法二、用双指针
核心思想：扩展右边界，缩短左边界，并适时更新数据。
209.长度最小的子数组
904.水果成篮
76.最小覆盖子串
209.长度最小的子数组
窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的连续子数组。 如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。 如何移动窗口的结束位置？
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针。
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= s) {
result = Math.min(result, right - left + 1);
sum -= nums[left++];
}
}
- 水果成篮
1, 使用map保存窗口中数字出现的次数，因为数字不是很大。可以使用数组模拟hash。
2，右指针移动时，如果发现是一个没有出现过的数字，就把cnt++
3，如果cnt个数超过了设定的窗口大小则开始收缩窗口
4，直到窗口中数字被减少到0. 此时将cnt–，退出收缩流程
5, 更新水果的 最大数目结果应该在right扩张的时候，在窗口缩小时不考虑。
public int totalFruit(int[] fruits) {
if(fruits.length <= 2) return fruits.length;
int ans = 0, left = 0;
HashMap window = new HashMap();
for (int right = 0; right < fruits.length; right++) {
window.put(fruits[right], window.getOrDefault(fruits[right], 0) + 1);
while (window.size() > 2){
window.put(fruits[left], window.getOrDefault(fruits[left], 0) - 1);
if(window.get(fruits[left]) == 0) window.remove(fruits[left]);
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
其他：
Java Map:
entrySet()的返回值也是返回一个Set集合，此集合的类型为Map.Entry。
Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry
由以上可以得出，遍历Map的常用方法：
Map map = new HashMap();
Iterator iterator = map.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry entry = iterator.next();
Object key = entry.getKey();
}
螺旋矩阵：
螺旋矩阵II
