前面写过2sum问题，回顾一下：给定一个数组，求其中和等于给定和的两个数。思想很简单，双指针的思想：对于排序数组，一个头指针一个尾指针，不断向中间压缩。如果数组是排序的，则时间复杂度为O(n)，空间复杂度为O(1)。由此可以K sum问题，如果看过《算法引论》这本书，我们可以把K sum问题归约到K-1 sum。举个例子，3 sum问题归约到2sum 问题。对于数组中的每一个数A[i]，对数组A[i+1…n]进行2sum求解，则时间复杂度为O(n^2)。类似的我们知道K sum问题的时间复杂度为O(n^k-1)。然而我们今天要讨论的却是另外一类问题。
问题一，给定一个只包含正数数组，求连续子数组和等于给定目标值的区间。和2 sum问题有点相同，也是双指针或者叫快慢指针，但是这里双指针初始化都指向头部。快指针先移动，当快慢指针区间内的和小于给定值时，移动快指针；否则移动慢指针。时间复杂度O(n)，值得注意的是，此时并没有数组排序好的要求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void subArraySum(int A[], int n, int target)
{
if(n==0)
return;
int head=0, tail=0, sum=A[0];
while(tail<n){
if(sum==target){
printf("%d\t%d\n", head, tail);
sum -= A[head++];
}
else if(sum < target){
++tail;
if(tail==n)
break;
sum += A[tail];
}
else
sum -= A[head++];
}
}
|
问题二、给定数组，包含正数、负数和0。求连续子数组和为0的最大区间。仔细比较问题一和问题二，可以发现此时数组的元素属性改变了。那么对应的方法也就不好用了。仔细分析，我们很容易想到方法，整体思想是类似的。首先对于数组A[1…n]定义数组sum[1…n]，sum[i]=A[0]+A[1]+…+A[i]=sum[i-1]+A[i]。所以我们可以在O(n)的时间内求得数组sum[1…n]。则很显然可以想到，对于区间[i,j]，如果其和为0，则有sum[j]=sum[i-1]。具体处理则只需要将数组sum[1…n]排序并且保持原下标不变，值得注意的是，由于数组sum[1…n]的值大小上下界是确定的，所以可以采用O(n)的桶排序，最后再遍历一遍桶就OK了。这里有一点可以说的就是桶排序的应用。其实我们并不需要将sum数组排好序，只要把sum数组放到对应的桶中，就可以了，然后处理每一个桶。对于桶i中的元素j，k,意义如下：sum[j]=sum[k]=i，而且桶中的元素是递增的（这个容易理解，因为我们是按sum从前到尾遍历的）。看下代码就都明白了。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
int BucketSort(int sum[], int n)
{
map<int, vector<int> >bucket;
for(int i=0; i<n; ++n)
bucket[sum[i]].push_back(i);
int maxInterval=0;
for(map<int,vector<int> >::iterator iter=bucket.begin(); iter!=bucket.end(); ++iter)
{
int sizev = iter->second.size();
maxInterval = max(iter->second[sizev-1]-iter->second[0], maxInterval);
}
return maxInterval;
}
int subArraySum0(int A[], int n)
{
if(n==0)
return 0;
int *sum = new int [n];
sum[0] = A[0];
for(int i=1; i<n; ++i)
sum[i] = sum[i-1]+A[i];
int ret = BucketSort(sum, n);
delete [] sum;
return ret;
}
``
问题三、问题二的变体，<span style="font-size: small;">当</span>追求的和不是0而是target的时候怎么办？前面的思路都是一样，后面的怎么处理呢？前面提到桶排序，则我们可以在桶上直接来求。比如对于buck[i]就是表示和为i的sum区间，则只要考查buck[i-target]和buck[i+target]就行了。处理的时候，我们可以从一个确界开始，比如下界就考察buck[i]和buck[i+target]，上界就考察buck[i]和buck[i-target]。
```c++
int BucketSort(int sum[], int n, int target)
{
map<int, vector<int> >bucket;
for(int i=0; i<n; ++n)
bucket[sum[i]].push_back(i);
int maxInterval=0;
for(map<int,vector<int> >::iterator iter=bucket.begin(); iter!=bucket.end(); ++iter)
{
map<int,vector<int> >::iterator pos=bucket.find(iter->first+target);
if(pos != bucket.end())
{
maxInterval = max(maxInterval, pos->second.back()-iter->second.front());
}
}
return maxInterval;
}
int subArraySumN(int A[], int n, int target)
{
if(n==0)
return 0;
int *sum = new int [n];
sum[0] = A[0];
for(int i=1; i<n; ++i)
sum[i] = sum[i-1]+A[i];
int ret = BucketSort(sum, n, target);
delete [] sum;
return ret;
}
|
问题四、输入数组A[]，包含正数、负数、0。求正数与负数个数相同的最长的子数组。如果能把这题和上面的联系起来的话，也可以很快想出解决方案。把sum数组换成diff[1…n]，diff[i]表示数组A[1…i]中正数比负数多的个数。这种方法说起来也简单，而且也不难理解。再或者，我们思维偷个懒，直接把正数替换成1，负数替换成-1，那么不就变成求子数组区间为0的问题了吗？想法很简单，代码也很简单，只需要遍历一遍数组，替换，然后调用上面的subArraySumN()函数就可以。
问题五、输入数组A[]，只包含0，1，求一个最长且0和1个数相等的子串。类似于问题四的替换思想，把0换成-1，又变成子数组和为0的区间问题了。
问题六、输入数组A[]，只包含数字1、2、3，不进行比较，求1，2，3的个数？运用上面的替换思想，可以有个很巧妙的解法。也就是把1替换成第一个素数也就是2，2替换成第二个素数3，3替换成第3个素数5。求个积，然后不断模+除就行了。这个也很容易理解，考虑到素数的性质：只能被自身和1整除。另外，任何一个整数的乘法因子都是素数。（如果不是素数，则可以继续分解）。下面看一个替换后的处理代码，替换的代码就不上了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void primeFunc(int A[], int n)
{
int sum=1;
for(int i=0; i<n; ++i)
sum *= A[i];
int factor[] = {2,3,5};
int num[] = {0,0,0};
int pos=0;
while(sum>1 && pos<3){
while(sum%factor[pos] == 0){
++num[pos];
sum /= factor[pos];
}
++pos;
}
for(int i=0; i<3; ++i)
cout << num[i] << endl;
}
|
这里只考虑了本题的情况，所以代码中出现了很多的幻数。正常设计成这样的接口void primeFunc(int A[], int n, int m)会好很多，m表示数组里有多少个不同的素数。另外还应该考虑到数的溢出问题，对于有些语言可能就需要自己构造大数类了。
对于代码中对于前置表达式++i的偏爱作一个说明：前置表达式直接在i上加1，然后再返回i。而后置表达式是先作一个i的副本，然后在i上加1，最后返回前面的副本。这个区别是很重要的。