ACM-学习记录-尺取法

本文最后更新于:2020年12月4日 晚上

题目

给定一个数组和一个数s,在这个数组中找一个区间,使得这个区间之和等于s。

例如:给定的数组int x[14] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};和一个s = 15。那么,可以找到的区间就应该有0到4, 3到5, 6到7.(注意这里的下标从0开始)

思路

对于这样的题,不用任何技巧就可以跑出结果,例如下面这个方法可能是大多数人能够想出来的:

先用一个数组sum[i]存放前i个元素的和,其实现用的是”递推思想“,注意,在编程中”递推“的思想用的特别多,一定要习惯这种思维方式。

1
2
3
4
sum[0] = x[0];//x为给定的原数组
for(int i = 1; i < n; i++){
sum[i] += sum[i-1];//递推思想
}

然后通过两层循环求解

1
2
3
4
for(int i = 0; i < n; i++)
for(int j = n-1; j >= 0; j--){
if(sum[j]-sum[i]==s) printf("%d---%d\n", i, j);
}

上面的方法当然是可行的,但是复杂度太高,有一个算法可以将其复杂度降为O(n)。这就是”尺取算法“。

尺取法:顾名思义,像尺子一样取一段,借用挑战书上面的话说,尺取法通常是对数组保存一对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧,是因为尺取法比直接暴力枚举区间效率高很多,尤其是数据量大的。

那么,用”尺取法“做上面这道题思路应该是这样的:

其实,这种方法很类似于蚯蚓的蠕动。

1)用一对脚标i, j。最开始都指向第一个元素。

2)如果区间i到j之和比s小,就让j往后挪一位,并把sum的值加上这个新元素。相当于蚯蚓的头向前伸了一下。

3)如果区间i到j之和比s大,就让sum减掉第一个元素。相当于蚯蚓的尾巴向前缩了一下。

4)如果i到j之和刚好等于s,则输入。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstdio>
using namespace std;

void findSUM(int *A, int n, int s){
int i = 0, j = 0;
int sum = A[0];
while(i <= j && j < n){
if(sum >= s){
if(sum == s) printf("%d---%d\n", i, j);
sum -= A[i];
i++;
}
else{
j++;
sum += A[j];
}
}
}

int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int m;
int x[14] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
cin >> m;
findSUM(x, 14, m);

return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!