-
区间定义有两种：左闭右闭[left, right]，左闭右开[left, right)。
-
while () 内的条件确定：是否有意义？左闭右闭时：left == right 时有意义，故循环条件确定为 left <= right
-
迭代时，left和right的移动，遵循循环不变量原则。
-
考虑到可能发生的整型溢出，求mid时提倡以下写法：
int mid = left + (right - left) / 2; int mid = left + ((right - left) >> 1);
- 经典题目：Leetcode704, Leetcode35
//Leetcode704
//经典二分查找：nums有序，查找target
//时间复杂度：O(logn)，其中 nn 是数组的长度。
//空间复杂度：O(1)。
//左闭右闭
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {//左闭右闭时，left == right时有意义
int mid = left + ((right - left) >> 1);
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
//左闭右开
public int search(int[] nums, int target){
int left = 0, right = nums.length;
while(left < right){
int mid = left + ((right - left) >> 1);
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid;//右开，遵循循环不变量原则
}else{
left = mid + 1;
}
}
return -1;
}
-
二分查找拓展：寻找左右边界，题目Leetcode34。分开考虑左边界与右边界。需要注意：
-
寻找右边界的方法findRightBorder 返回值为实际右边界 + 1，即最小的大于target的数的下标。寻找左边界的方法findLeftBorder 返回值为实际左边界 - 1，即最大的小于target的数的下标。
-
寻找右边界时，向右迭代的条件含有等号，寻找左边界时，向左迭代的条件含有等号。
-
寻找右边界时，向右迭代时更新右边界为left，寻找左边界时，向左迭代时更新左边界为right。在最后一次迭代后，left = right + 1。寻找右边界时，此时right指向最后一个target，即实际右边界，left指向实际右边界 + 1。寻找左边界时，此时left指向最前一个target，即实际左边界，right指向实际左边界 - 1。
-
共有三种情况：1）target存在于数组中；2）target不存在于数组中，且target < nums[0] || target > nums[n-1]；3）target不存在于数组中，且targrt > nums[0] && target < nums[n-1]。
-
//Leetcode34
//时间复杂度：O(logn) 两次二分查找。
//空间复杂度：O(1)。
//nums有序，返回target的左右边界下标
public int[] searchRange(int[] nums, int target) {
int rightBorder = findRightBorder(nums, target);
int leftBorder = findLeftBorder(nums, target);
//情况2：target < nums[0] 或 target > nums[n-1]
//情况3：target不满足情况2，但是在数组中不存在
if(rightBorder == -2 || leftBorder == -2 || rightBorder - leftBorder <= 1){
return new int[]{-1, -1};
}
//情况1：target存在在数组中
return new int[]{leftBorder + 1, rightBorder - 1};
}
//返回右边界：大于target的第一个数的下标
public int findRightBorder(int[] nums, int target){
int rightBorder = -2;
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(target >= nums[mid]){//注意：寻找右边界时，向右迭代的条件含有等号
left = mid + 1;
rightBorder = left;//寻找右边界时，向右迭代时更新右边界为left
}else{
right = mid - 1;
}
}
return rightBorder;
}
//返回左边界：小于target的第一个数的下标
public int findLeftBorder(int[] nums, int target){
int leftBorder = -2;
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(target <= nums[mid]){//注意：寻找左边界时，向左迭代的条件含有等号
right = mid - 1;
leftBorder = right;//寻找左边界时，向左迭代时更新左边界为right
}else{
left = mid + 1;
}
}
return leftBorder;
}
2. 双指针
-
移除元素 Leetcode27 ，可采用双指针法，两种解法。1）前后指针 2）快慢指针。
-
前后双指针：前指针从左向右遍历，查找到target时，将其值替换为后指针位置的值（需要判断后指针位置的值是否是target，如果是，后指针需要自减，再重新进入循环判断），直至前指针超过后指针，退出循环。期间需要维护count用来记录新数组的长度，初始值为0，每当 i ++ 时，count ++ 。
//Leetcode27 //前后双指针 //时间复杂度：O(n)。 //空间复杂度：O(1)。 public int removeElement(int[] nums, int val) { int i = 0, j = nums.length - 1; int count = 0; while(i <= j){ if(nums[i] == val){ if(nums[j] != val){ nums[i] = nums[j]; i++; j--; count++; }else{ j--; } }else{ i++; count++; } } return count; } -
快慢双指针：快指针和慢指针初始位于0下标位置，判断快指针的值是否是val，如果不是就其赋给将慢指针位置的值，慢指针后移，如果是则不赋值。每次循环快指针必须后移。当快指针等于nums的长度时退出循环（刚好越界），此时慢指针所处的下标位置即新数组长度（刚好越界）。
//快慢双指针 //时间复杂度：O(n)。 //空间复杂度：O(1)。 public int removeElement(int[] nums, int val) { int fast = 0, slow = 0; while(fast < nums.length){ if(nums[fast] != val){ nums[slow] = nums[fast]; slow++; } fast++; } return slow; }
-
-
有序数组的平方 Leetcode977，采用双指针法。由于nums为非递减序列，且包含负数，则可以采用前后双指针，循环判断两指针位置处的值谁平方（绝对值）更大，填入新数组。注意：填入新数组时需要从后向前填入，以确保新数组为非递减序列。
//Leetcode977 //双指针法 //时间复杂度：O(n)。 //空间复杂度：O(1)。??? public int[] sortedSquares(int[] nums) { int i = 0, j = nums.length - 1; int[] res = new int[nums.length]; for(int k = nums.length - 1; k >= 0; k--){ if(Math.abs(nums[i]) > Math.abs(nums[j])){ res[k] = nums[i] * nums[i]; i++; }else{ res[k] = nums[j] * nums[j]; j--; } } return res; }
-
长度最小的子数组 Leetcode209，采用滑动窗口法，sum记为窗口内数值之和。如果sum < target，说明需要扩展窗口，right右移。如果sum >= target，说明可能需要压缩窗口，left左移。期间维护res为满足要求（sum >= target）窗口的最小长度。
//Leetcode209 //滑动窗口法 //时间复杂度：O(n)。 //空间复杂度：O(1)。 public int minSubArrayLen(int target, int[] nums) { //int n = nums.length; int left = 0; int res = Integer.MAX_VALUE; int sum = 0; for(int right = 0; right < nums.length; right++){ sum += nums[right]; while(sum >= target){ res = Math.min(res, right - left + 1); sum -= nums[left]; left++; } } return res == Integer.MAX_VALUE ? 0 : res; }
-
经典题目：螺旋矩阵 Leetcode54，螺旋矩阵 II Leetcode59。前者为顺时针螺旋返回m × n矩阵的元素，后者为顺时针螺旋填入n × n方阵的元素，可采用设定边界的模拟法或前闭后开的循环不变量原则法。
-
设定边界l, r, t, b 分别表示未填入（未返回）区域的左、右、上、下边界。
-
在从左向右的遍历后，t++ 缩小上边界；从上向下遍历后，r-- 缩小右边界；从右向左的遍历后，b-- 缩小下边界；从下向上遍历后，l++缩小左边界。
-
循环条件可以从两方面入手：一是用count记录遍历过的元素个数，需要count <= maxVal。二是用l <= r && t <= b。（需要多加考虑该处，特别是最后就剩一个元素或一行（一列）元素时，何时退出循环）
//Leetcode54： //时间复杂度：O(mn)。 //空间复杂度：O(1)。??? public List
spiralOrder(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; List list = new ArrayList<>(); int l = 0, r = n - 1, t = 0, b = m - 1; int count = 0; int maxVal = n * m; while(l <= r && t <= b){ for(int i = l; i <= r && count++ < maxVal; i++){ list.add(matrix[t][i]); } t++; for(int i = t; i <= b && count++ < maxVal; i++){ list.add(matrix[i][r]); } r--; for(int i = r; i >= l && count++ < maxVal; i--){ list.add(matrix[b][i]); } b--; for(int i = b; i >= t && count++ < maxVal; i--){ list.add(matrix[i][l]); } l++; } return list; } //Leetcode59： //时间复杂度：O(mn)。 //空间复杂度：O(1)。??? public int[][] generateMatrix(int n) { int[][] matrix = new int[n][n]; int maxVal = n * n; int count = 1; int l = 0, r = n - 1, t = 0, b = n - 1; while(count <= maxVal){ for(int i = l; i <= r; i++){ matrix[t][i] = count++; } t++; for(int i = t; i <= b; i++){ matrix[i][r] = count++; } r--; for(int i = r; i >= l; i--){ matrix[b][i] = count++; } b--; for(int i = b; i >= t; i--){ matrix[i][l] = count++; } l++; } return matrix; }
