前缀和
【
适?于快速、频繁地计算?个索引区间内的元素之和，
原始数组的元素不发生变化】
在初始化的时候定义一个数组用来存储每个节点对应的元素之和，在需要求解特定索引区间时只需要用简单的加减法就可以得到结果。可以大大降低时间复杂度。
差分数组
【适?于频繁对原始数组的某个区间的元素进?增减，原始数组的元素发生变化】
Difference()：初始化差分数组diff，diff中存储的是相邻元素之间的差值（后一个减去前一个）；
increment()：根据题目要求对diff进行调整；
如：对区间[i, j]（要注意题目中改变的元素是否包括右边界的元素）的元素增加1，则只需要
diff[i] += 1；????????根据j的索引位置不同，有不同的情况，如果j + 1 >= diff.length，表示对i之后的所有元素都增加1，只需要执行上面那一条语句就可以；如果j + 1 <? diff.length，表示还需要对j后面的元素进行处理，否则j后面的元素也会增加1。
if (j + 1 < diff.length) {
diff[j + 1] -= 1;
}result()：根据差分数组diff复原数组nums。
// 差分数组?具类
class Difference {
// 差分数组
private int[] diff;
/* 输??个初始数组，区间操作将在这个数组上进? */
public Difference(int[] nums) {
if (nums.length == 0) return ;
diff = new int[nums.length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i,j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}滑动窗口
大佬给出的框架：
/* 滑动窗?算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移?窗?的字符
char c = s[right];
// 右移窗?
right++;
// 进?窗?内数据的?系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗?是否要收缩
while (window needs shrink) {
// d 是将移出窗?的字符
char d = s[left];
// 左移窗?
left++;
// 进?窗?内数据的?系列更新
...
}
}
}自己改了一个Java版本的：
/* 滑动窗?算法框架 */
void slidingWindow(string s, string t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
char[] ct = t.toCharArray();
//先把t中的字符及个数存入need中
for (char c : ct) need.put(c, need.getOrDefault(c, 0) + 1);
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移?窗?的字符
char c = s.charAt(right);
// 右移窗?
right++;
// 进?窗?内数据的?系列更新
...
/*** debug 输出的位置 ***/
System.out.println("window: [" + left + "," + right + "]");
/********************/
// 判断左侧窗?是否要收缩
while (window needs shrink) {
// d 是将移出窗?的字符
char d = s.charAt(left);
// 左移窗?
left++;
// 进?窗?内数据的?系列更新
...
}
}
}如果不用Map存储，选择用数据存储，总结了一个大致的框架
/* 滑动窗?算法框架 */
void slidingWindow(string s, string t) {
// 长度定位128是因为使用ASCII码存储字符
int[] need = new int[128];
char[] ct = t.toCharArray();
//先把t中的字符及个数存入need中
for (char c : ct) need[c]++;
int left = 0, right = 0;
int cnt = t.length();
while (right < s.length()) {
// c 是将移?窗?的字符
char c = s.charAt(right);
// 如果c是需要的字符
if (need[c] > 0) {
cnt--;
}
need[c]--;
// 进?窗?内数据的?系列更新
...
if (cnt == 0) {
// 此时说明字符达到了要求
while (left < right && need[s.charAt(left)] < 0) {
// 此时是在收缩窗口，先去除不是t中的字符
need[s.charAt(left)]++;
left++;
}
if (// 通常这里是判断当前窗口是否符合题意) {
...
}
// 不是t中的都处理完后，当前left指向的就是t中需要的，所以cnt也要变化
need[s.charAt(left)]++;
left++;
cnt++;
}
right++;
}
}算法小抄https://labuladong.gitee.io/algo/
https://labuladong.gitee.io/algo/