中国建设银行老版本下载官方网站,证件照在线制作,如何申请免费的网站空间,石家庄有什么好玩的地方1. 双指针 双指针算法的核心思想#xff1a;将暴力解法的时间复杂度#xff0c;通常是O(N*N)#xff0c;通过某种特殊的性质优化到O(N)。 做题思路#xff1a;先想想暴力解法的思路#xff0c;然后分析这道题的特殊性质#xff0c;一般是单调性。然后得出双指针算法的思路…1. 双指针 双指针算法的核心思想将暴力解法的时间复杂度通常是O(N*N)通过某种特殊的性质优化到O(N)。 做题思路先想想暴力解法的思路然后分析这道题的特殊性质一般是单调性。然后得出双指针算法的思路。 双指针算法的模板 for(int i 0; i ; i) { while(j i check(i, j)) j; //具体题目的解题思路 }、 1.1 例题 给定一个长度为 n 的整数序列请找出最长的不包含重复数数字的最长子序列输出它的长度。 输入格式 第一行包含整数 n 。 第二行包含 n 个整数均在0 ~ 100000范围内表示整数序列。 输出格式 共一行包含一个整数表示最长的不包含重复数字的连续子序列的长度。 数据范围 1 n 100000 按照上面介绍的解题思路我们先看看暴力解法怎么做的两层for循环外层循环在遍历数组时对于外层循环遍历的每一个值内层循环都会从该位置开始去遍历通过检查区间内是否存在重复数字更新结果。显然这种解法的事件复杂度为O(N*N)。伪代码如下 for (int i 0; i n; i) { for (j i 1; j n; j) { if (!check(i, j)) ret max(ret, i - j 1); } } 其中n为数组的长度check为检查区间 [ i, j ] 中的元素是否存在重复的数字如果不存在更新结果保存到ret中。 双指针同样根据上面提供的解题思路我们尝试从暴力解法中分析出单调性。嗯双指针的左侧指针在整个查找过程中是单调的。怎么理解呢
下面以一个具体的例子1,2,2,3,5 来分析哈 现在我们已经知道了双指针的大致思路了但是好像还没有弄清除单调性从何而来。对于本题单调性就是在 i 向右找更大的满足要求的更长区间时j不可能存在向前动 (j--) 的情况。即本题中 j 具有单调性。 弄清除了这些我们只需要知到怎么判定一个区间中是否有重复元素就行了。我们可以初始化一个数组a遍历原数组b, 得到的值假设为s就让 a[s] 1代表这个数字出现了一次。注意当一个区间中没有重复元素时i那么只有原数组中下标为 i 的 的值才会是重复的元素因此我们只需要判断 a[b[i]] 的值是否是大于 1 即可。这就是模板中的 check 。另外本题中不要 i j 这个条件因为 i j 时区间 [j, i] 中就没有重复的元素了i然后就会加一即 j 是不会大于 i 的。
当区间内存在重复元素时j的同时要将 a[b[j]]--少了一个数字嘛。 现在可以写代码啦
int main()
{const int N 100000;//原数组int b[N];//统计数字出现次数的数组int a[N] { 0 };//用于保存最大的区间长度int ret 0;int j 0;//读入数据int n;scanf(%d, n);for (int i 0; i n; i){scanf(%d, b[i]);}//核心算法for (int i 0; i n; i){a[b[i]];while (a[b[i]] 1){//少一个数字次数减一a[b[j]]--;j;}//更新结果ret ret i - j 1 ? ret : i - j 1;}//打印结果printf(%d\n, ret);system(pause);return 0;
}
1.2 小试牛刀来源Acwing
