二分查找

适用场景

有序数组寻找目标值

基本思想

public int binarySearch( int[] nums, int target ){

//[5,7,7,8,8,10]

int left = 0;

int right = nums.length - 1;

int index = nums.length;

while( left <= right ){

int mid = ( left + right ) / 2;

if( nums[ mid ] > target ){

right = mid - 1;

index = right;

}

else{

left = mid + 1;

}

}

return index;

}

时间复杂度

O(log n)

特殊题型

搜索旋转排序数组 （例：[4,5,6,7,0,1,2]

搜索旋转排序数组局部有序。二分法之后拆分成两个数组、总存在一个数组是有序的，判断目标值是否存在于这个有序数组中，如果不在，则再次二分剩下的数组。

搜索二维数组

public boolean searchMatrix(int[][] matrix, int target) {

int m = matrix.length, n = matrix[0].length;

int low = 0, high = m * n - 1;

while (low <= high) {

int mid = (high - low) / 2 + low;

int x = matrix[mid / n][mid % n];

if (x < target) {

low = mid + 1;

} else if (x > target) {

high = mid - 1;

} else {

return true;

}

}

return false;

}

双指针

有序链表去掉重复数据

思想：哑节点作为前置节点，定义哑节点为当前节点，判断next和next的next节点是否为空。如果不为空则判断next的val是否等于next的next的val，如果值想的则移动cur.next指针，将cur.next.next赋给cur.next，否则移动cur指针。

三数之和

思想：「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。也就是说，我们枚举的三元组(a,b,c) 满足a≤b≤c，保证了只有(a,b,c) 这个顺序会被枚举到，而(b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。举个例子，如果排完序的数组为[0, 1, 2, 2, 2, 3]我们使用三重循环枚举到的第一个三元组为(0,1,2)，如果第三重循环继续枚举下一个元素，那么仍然是三元组(0,1,2)，产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素，即数组中的最后一个元素3，枚举三元组(0,1,3)这种方法的时间复杂度仍然为 o(n的3次方），毕竟我们还是没有跳出三重循环的大框架。然而它是很容易继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足a+b+c=0。当第二重循环往后枚举一个元素b' 时，由于b'>b，那么满足 a'+b'+c'=0 的一定有c'<c，即c'在数组中一定出现在c的左侧。也就是说，我们可以从小到大枚举b，同时从大到小枚举c，即第二重循环和第三重循环实际上是并列的关系。

比较含退格的字符串

获取string字符串长度，for循环。string.charAt 判断当前char是否等于#，不是则加入新的数组，否则删除新数组的最末位数字。

区间列表的交集

方法：归并区间

取两个区间列表的交集首先，二维数组的第二项是固定的，只能有两位先判断a[i][0]和b[j][0]的大小关系、再判断a[i][1]和b[j][1]的大小关系因为如果a[0]是最小的，那么只能和b[0]相交，因此用指针后移一位，模拟去除a[0]。

盛水最多的容器

双指针题目，盛水面积等于min（边界1，边界2）*宽度因此保存所有的面积，并返回最大值就可以了。