20230724
简单的求和
做题原因
之前TLE30和TLE60，一直没有做出来
做题过程
- 想到了尺取法，重新听了尺取法的课，看了尺取法的模板。
- 看了之前错误的代码，决定沿用之前使用map的方法，但是在找不出之前的错误，重新写了一遍代码
- 交上去AC
解题思路
-
首先输入的元素是不需要按照它本来的顺序的（可以重新排序）
-
需要给元素进行排序（set或者map，但是set会去重，所以选择map）
-
因为是计算加法，所以只要计算过一次，所有相同的元素都使用（map）
-
需要记录元素的个数（map）
根据以上三点，我选用了map -
相加刚好等于k，所以比k大或者比k小都需要调整范围
-
元素是排好序的
根据以上两点，我选择了尺取法
代码实现
auto left = mp.begin();//设置左指针，map的第一个元素
auto right = mp.end(); right--;//设置右指针，map的最后一个元素
while (left != right) {//当左指针和右指针不相等时（相等考虑的情况不一样）
if (left->first + right->first == k) {//如果相加等于k
ans += left->second * right->second;//做指针的元素任意取出一个和右指针的元素任意取出一个进行搭配都可以，所以时乘法
left++;//将左指针后移
if (left == right) {//如果相等，循环结束，和上面的判断条件一样
break;
}
right--;//因为这两个数相加刚好等于k，所以任何一个数加减都不会再等于k，所以这里面右指针也要向前移动
} else if (left->first + right->first > k) {//如果大于
right--;//那么右指针向前移动，减少其中一个数
} else if (left->first + right->first < k) {//如果小于
left++;//那么左指针向后移动，增大第一个数
}
}
if (2 * left->first == k) {//如果相等，那么要考虑的就是这个数乘2是否等于k
ans += left->second * (left->second - 1) / 2;//从这个数里面取出任意一个，这个数的数量减少1，然后再从这些数里面取出一个，但为了避免同样的a和b，第一次取出a然后取出b，第二次取出b然后取出a的情况，需要除以2
}
长度最小的子数组
做题原因
练习尺取法
做题思路
因为数据范围为\(1\le n\le 3\times 10^{5}\)，
所以每个都遍历的话会就是\(O\left ( n^{2} \right )\) ，
肯定会TLE，
所以想到了尺取法。
如果只遍历一端的话，
那么时间复杂度大概在\(O\left ( n\log_{}{n} \right )\)左右，
不会TLE，
所以我们只需要遍历每个端点最短的的\(\ge s\)的子数组的长度就结束这个端点的遍历（因为后面即便有\(\ge s\)长度也比之前找到的长，没有找的必要），
然后把它和目前所有端点最短的比较