二分搜索
. - 力扣（LeetCode）
使用场景
前提是数组为有序数组，同时题目还强调数组中无重复元素。
因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。
模板
左闭右闭的区间
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。因为我们是左闭右闭的区间，举个例子，【1，1】，这个时候我们left==right是有意义的，是合法的，所以我们循环的时候要left <= right
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1。因为我们比较左右边界的时候，left和right都是可以取到的。所以nums【middle】一定不是target
左闭右开区间
- while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的。请看上面左闭右闭到情况的解释
- if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]。因为我们比较left和right的时候，right是取不到的，就是说mid取不到right，也就是说我们仍需要拿right所在的值去看是不是等于target。所以mid更新为right
class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target) {return mid;}else if (nums[mid] < target) {left = mid + 1;}else { // nums[mid] > targetright = mid;}}// 未找到目标值return -1;}
}快慢指针（双指针）
基础模板
27. 移除元素 - 力扣（LeetCode）
class Solution {public int removeElement(int[] nums, int val) {// 快慢指针int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {if (nums[fastIndex] != val) {nums[slowIndex] = nums[fastIndex];slowIndex++;}}return slowIndex;}
}另外题型1
977. 有序数组的平方 - 力扣（LeetCode）
class Solution {public int[] sortedSquares(int[] nums) {// 定义左右指针int left = 0;int right = nums.length - 1;// 定义一个新的数组储存排序后的元素int ret[] = new int[nums.length];// 定义一个指针始终指向数组最后int end = nums.length - 1;while(left <= right){if(nums[left] * nums[left] > nums[right] * nums[right]){ret[end] = nums[left] * nums[left];left++;}else{ret[end] = nums[right] * nums[right];right--;}end--;}return ret;}
}滑动窗口（另类的双指针）
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
这里要求求数组的子序列的参数---长度，可以想到滑动窗口
209. 长度最小的子数组 - 力扣（LeetCode）
class Solution {public int minSubArrayLen(int target, int[] nums) {// 窗口左右边界int left = 0;int right = 1;// 定义窗口内数组的大小int sum = 0;int ret = Integer.MAX_VALUE;// 初始右边界for (; right < nums.length; right++) {sum += nums[right];while (sum >= target) {ret = Math.min(ret, right - left + 1);sum -= nums[left];left++;}}return ret == Integer.MAX_VALUE ? 0 : ret;}
}螺旋矩阵
59. 螺旋矩阵 II - 力扣（LeetCode）
统一左闭右开，遵循循环不变量
class Solution {public int[][] generateMatrix(int n) {// 定义二维数组int ret[][] = new int[n][n];// 圈数int loop = 1;// 行和列的迭代int i;int j;// 行和列的起始位置int startX = 0;int startY = 0;// 每一行走的步数,每一条边的长度int offset = 1;// 记录每一格的结果int count = 1;while(loop <= n / 2){// 该圈的上面那一行for(j = startY; j < n - offset; j++){ret[startX][j] = count;count++;}// 右边的那一列for(i = startX; i < n - offset; i++){ret[i][j] = count;count++;}// 下面那一行for(; j > startY; j--){ret[i][j] = count;count++;}for(; i > startX; i--){ret[i][j] = count;count++;}// 走完一圈后更新相应的参数startX++;startY++;offset++;loop++;}if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值ret[startX][startY] = count;}return ret;}
}前缀和
用于求涉及计算区间和的问题
前缀和的思路其实很简单，我给大家举个例子很容易就懂了。
例如，我们要统计 vec[i] 这个数组上的区间和。
我们先做累加，即 p[i] 表示 下标 0 到 i 的 vec[i] 累加 之和。
题一：
58. 区间和（第九期模拟笔试） (kamacoder.com)
import java.util.*;// 主类
public class Main {public static void main(String[] args) {// 创建输入扫描器Scanner input = new Scanner(System.in);// 读取数组长度int n = input.nextInt();int arr[] = new int[n]; // 用于存储输入的整数数组int sumArr[] = new int[n]; // 用于存储前缀和数组int sum = 0; // 用于计算总和// 输入数组元素并计算前缀和for (int i = 0; i < n; i++) {int temp = input.nextInt(); // 读取一个整数arr[i] = temp; // 存储到数组中sum += temp; // 更新总和sumArr[i] = sum; // 存储当前的前缀和}// 处理后续输入的查询while (input.hasNextInt()) {int a = input.nextInt(); // 读取起始索引int b = input.nextInt(); // 读取结束索引int sumInRound; // 用于存储查询区间的和// 计算区间和if (a == 0) {sumaInRound = sumArr[b]; // 从开头到 b 的和} else {sumInRound = sumArr[b] - sumArr[a - 1]; // 从 a 到 b 的和}System.out.println(sumInRound); // 输出结果}// 关闭输入扫描器input.close();}
}题二：
44. 开发商购买土地（第五期模拟笔试） (kamacoder.com)
import java.util.*;public class Main {public static void main (String[] args) {Scanner input = new Scanner(System.in);// 读取矩阵的行数 n 和列数 mint n = input.nextInt();int m = input.nextInt();// 创建一个 n x m 的二维数组 map 用于存储矩阵int map[][] = new int[n][m];int sum = 0; // 用于存储矩阵所有元素的总和// 读取矩阵元素并计算总和for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {map[i][j] = input.nextInt(); // 读取元素sum += map[i][j]; // 累加总和}}// 创建一维数组 XSum，用于存储每一行的和int XSum[] = new int[n];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {XSum[i] += map[i][j]; // 计算每行的和}}// 创建一维数组 YSum，用于存储每一列的和int YSum[] = new int[m];for (int j = 0; j < m; j++) {for (int i = 0; i < n; i++) {YSum[j] += map[i][j]; // 计算每列的和}}// 初始化最小差值 ret 为最大整数int ret = Integer.MAX_VALUE;int currentXSum = 0; // 当前累加的横向和// 计算横向切割的最小差值for (int i = 0; i < n; i++) {currentXSum += XSum[i]; // 累加当前行的和// 更新最小差值ret = Math.min(ret, Math.abs(sum - 2 * currentXSum));}int currentYSum = 0; // 当前累加的纵向和// 计算纵向切割的最小差值for (int j = 0; j < m; j++) {currentYSum += YSum[j]; // 累加当前列的和// 更新最小差值ret = Math.min(ret, Math.abs(sum - 2 * currentYSum));}// 输出最小差值System.out.println(ret);}
}
总结
