刷题疑惑3
1、等值距离和（340周赛B）：有时间复杂度的要求，采用前缀和策略，保存在一个前缀和数组中，序列是从左...
2023-04-10
【资料图】
1、等值距离和（340周赛B）：有时间复杂度的要求，采用前缀和策略，保存在一个前缀和数组中，序列是从左往右递增的，所以可以将其分为左侧和右侧分开计算，模板题；同有序数组中差绝对值之和；
既然数组是非递减有序的，那么a[i]左边的元素一定不大于它本身，右边的元素一定不小于它本身；我们先计算出i位置（包含i）的前缀和pre[i]；a[i]与它左侧的所有元素绝对值差的和，等于i * a[i] - pre[i-1];；a[i]与它右侧的所有元素绝对值差的和，等于pre[a.length-1] - pre[i] - (a.length-1-i) * nums[i]；
2、判断是否是质数：采用平方根方法，1不是质数，所以从2开始计算；
bool isPrime(int num){ if(num <= 1) return false; for(int i = 2;i*i <= num; ++i){ if(num % i == 0) return false; } return true;}3、最小化数对的最大差值：二分思想+贪心；周赛常考的知识点；看到最大值最小的问题就想二分方法；先排序，相邻的元素差值一定最小，所以转化为最多选几个数对使得最大差值不超过x，x就是我们要枚举的元素；如果我们选了大于等于p个数对，那么该答案就通过检验；多写写类似题目，若将 排序后相邻元素的差值记录下来，该题还可以转化为 打家劫舍；
4、跳跃游戏Ⅱ：动规做时间复杂度高；贪心好一些；起始时只能跳一次，将能跳到的范围内的值挨个枚举，更新最大值；
5、
