算法
1.差分数组+前缀和
1589. 所有排列中的最大和 - 力扣（LeetCode）
对于每一次遍历都有m个数需要加1，如果对这些数遍历，则需要O（m）复杂度，此时可以记录这m个数的差分数组：
这样就可以把时间复杂度缩小到O(1)，之后求前缀和就可以得到原来的数组。
2.线性筛（欧拉筛）求素数
public int[] findPrime(int max){
boolean[] isNotPrime = new boolean[max];//数的范围
int[] primes = new int[n];//质数大小
int cnt = 0;
for( int i = 2; i < max; i++){
if(!isNotPrime[i]) primes[cnt++] = i;
for(int j = 0;j < cnt && primes[j] * i < max;j++){
isNotPrime[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
return primes;
}
3.二分查找
求边界
2563. 统计公平数对的数目 - 力扣（LeetCode）
技巧：
求一个数在区间[left，right]时，可以转化为：(<=right) - (<= left - 1)
求两个数之和在区间[left，right]时，可以转化为：
遍历其中一个数num1，求(<=right - num1) - (<= left - num1 - 1)
//普通的二分查找 left = -1; right = length; 开区间
public int binarySort(int[] nums, int left, int right, int value){
while(left + 1 < right) {
int mid = (left + right) >>> 1;
if(value < nums[mid]){
right = mid;
} else if (value == nums[mid]) {
return mid;
} else{
left = mid;
}
}
return -1;
}
//通用模板>=
//left = -1; right = length; 开区间
public int binarySearch(int[] nums, int left, int right, int value){
while(left + 1 < right) {
int mid = (left + right) >>> 1;
if(value <= nums[mid]){
right = mid;
} else{
left = mid;
}
}
return right;
}
//求>: binarySort(nums,left,right,value + 1);
//求<: binarySort(nums,left,right,value) - 1;
//求<=: binarySort(nums,left,right,value + 1) - 1;
最大化最小值/最小化最大值
2439. 最小化数组中的最大值 - 力扣（LeetCode）
第k大/第k小
以上两种的思路：
利用二分查找符合条件的数，根据是否满足题意来收缩数的范围！
、
题解：
根据容斥原理，给定一个能被a或b整除的数num：
n = num/a + num/b - num/(a和b的最小公倍数)
所以该题目可以利用二分查找，通过容斥原理计算对应第几个神奇数字，如果该数大于预期的n，则缩小数的范围继续进行二分查找。
class Solution {
public int nthMagicalNumber(int n, int a, int b) {
long left = Math.min(a,b);
long right = (long)n * Math.min(a,b);
while(left + 1 < right){
long mid = (left + right) >>> 1;
long cnt = mid / a + mid / b - mid * greatestCommonDivisor(a,b)/(a * b);
if(cnt >= n){
right = mid;//缩小数的范围
}else{
left = mid;
}
}
return (int)(right % 1000000007L);
}
private int greatestCommonDivisor(int a, int b){//最小公倍数
int r = Math.max(a,b);
int l = Math.min(a,b);
while(l != 0){
int temp = l;
l = r % l;
r = temp;
}
return r;
}
}
4.双指针
快慢指针
相向指针
题解：
利用双指针从数组两侧向中间靠拢，根据两端线的长度进行收缩，以left > right为例，有两种情况：
①如果移动left指针，容量可能会变小（移动后的left < right）或者不变（移动后的left >=right）；
②如果移动right指针，容量可能会变大（移动后的right > 原来的right）、变小（移动后的right < 原来的right）或者不变（移动后的right不变）；
所以要想求得最优解，可以通过移动线的长度较小的那一段，求所有面积的最大值即可。
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = -1;
while(left < right){
int area = (right - left) * Math.min(height[left], height[right]);
maxArea = Math.max(maxArea,area);
if(height[left] < height[right]){//缩小线段长度比较小的那一段
left++;
}else{
right--;
}
}
return maxArea;
}
}
滑动窗口
1004. 最大连续1的个数 III - 力扣（Leetcode）
题解