新网金商网站,怎么做网站关键词推广,想自学软件开发难吗,电子购物网站开发在一些数组或者字符串我们需要遍历子序列#xff0c;可能要用到两个指针#xff08;我们称为起始指针和终止指针#xff09;进行双层遍历#xff0c;内层终止指针满足条件时跳出内层循环#xff0c;然后起始指针前进#xff0c;回溯终止指针到起始指针#xff0c;以此继…在一些数组或者字符串我们需要遍历子序列可能要用到两个指针我们称为起始指针和终止指针进行双层遍历内层终止指针满足条件时跳出内层循环然后起始指针前进回溯终止指针到起始指针以此继续进行遍历然而这样效率比较低我们可能进行了很多不必要的比较。有没有可能只进行一次遍历呢滑动窗口提供了一个很好的思路。
在滑动窗口算法中我们要解决以下问题
窗口内是什么
窗口就是满足条件的子序列。
如何移动窗口的起始位置
当前窗口的值满足条件了窗口的起始指针就要向前移动了也就是该缩小窗口。
如何移动窗口的结束位置
窗口的结束位置就是遍历数组的终止指针也就是一次遍历for循环的索引。把整个数组遍历完终止指针到了最后一个索引移动窗口就结束了。 代码模板
int i 0, j 0;//i是终止指针j是起始指针
for (; i s..size(); i)//s是序列i是一遍遍历的终止指针
{//对s[i]的操作// 窗口满足条件就更新数据起始指针要移动while(窗口满足条件){//记录或更新数据...//起始指针移动一位j;//记录或更新数据...}//返回结果练习题牛客网-牛牛的数组匹配 牛牛刚学会数组不久他拿到两个数组 a 和 b询问 b 的哪一段连续子数组之和与数组 a 之和最接近。 如果有多个子数组之和同样接近输出起始点最靠左的数组。 输入描述 第一行输入两个正整数 n 和 m 表示数组 a 和 b 的长度。 第二第三行输入 n 个和 m 个正整数表示数组中 a 和 b 的值。 输出描述 输出子数组之和最接近 a 的子数组 示例1 输入 2 6 30 39 15 29 42 1 44 1 输出 29 42 示例2 输入 6 1 50 47 24 19 46 47 2 输出 2 #include iostream
#include cmath
using namespace std;int main() {int n, m;cin n m;int a[n], b[m];int sum_a 0; int sum_b 0;for (int i 0; i n; i){cin a[i];sum_a a[i];}for (int i 0; i m; i){cin b[i];}int j 0;int left 0, right 0;int res abs(b[0] - sum_a);//初始化b子序列和sum_b和sum_a的差for (int i 0; i m; i){sum_b b[i];while (sum_b sum_a)//找到sum_b中超过sum_a的分界线sum_b-b[i]sum_asum_bsum_a{if (sum_b - b[i] 0) //sum_b由两个及以上的数相加而成sum_b sum_a{if (abs(sum_b - b[i] - sum_a) abs(sum_b - sum_a))//sum_b-b[i]比sum_b更接近sum_a{if (abs(sum_b - b[i] - sum_a) res)//找到更接近sum_a的和sum_b - b[i]更新起始指针和终止指针{right i - 1;left j;res abs(sum_b - b[i] - sum_a);}sum_b - b[j];}else if (abs(sum_b - b[i] - sum_a) abs(sum_b - sum_a))//sum_b比sum_b-b[i]更接近sum_a{if (abs(sum_b - sum_a) res)//找到更接近sum_a的和sum_b更新起始指针和终止指针{right i;left j;res abs(sum_b - sum_a);}sum_b - b[j];}}else //sum_b由一个数相加而成sum_b sum_a{right i;left j;res abs(sum_b - sum_a);sum_b - b[j];}}if ((i m - 1) (j 0))//排除b数组所有数之和都小于a数组之和情况{right i;left j;} }for (int i left; i right; i)cout b[i] ;
}力扣的209.长度最小的子数组也是滑动窗口的典型应用也可以想想。解法在代码随想录有详解就不赘述了 代码随想录-209.长度最小的子数组
