Don't Panic! » 关于部分数组固定和的一类问题解析
前面写过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)，值得注意的是，此时并没有数组排序好的要求。
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从前到尾遍历的）。看下代码就都明白了。
/用map实现桶排序
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;
}
问题三、问题二的变体，当追求的和不是0而是target的时候怎么办？前面的思路都是一样，后面的怎么处理呢？前面提到桶排序，则我们可以在桶上直接来求。比如对于buck[i]就是表示和为i的sum区间，则只要考查buck[i-target]和buck[i+target]就行了。处理的时候，我们可以从一个确界开始，比如下界就考察buck[i]和buck[i+target]，上界就考察buck[i]和buck[i-target]。
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 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表示数组里有多少个不同的素数。另外还应该考虑到数的溢出问题，对于有些语言可能就需要自己构造大数类了。
关于部分数组固定和的一类问题解析续
给定整数数组A[1…n]，判断是否可以从中选出若干个数，使它们的和恰好为K。比如A[]={1,2,4,7}，K=13。应该返回2,4,7。
先介绍一种简单的方法：状态搜索，对于数组A[]中的元素只有两种可能：选或者不选。所以我们可以得到下面这张图，然后对这张图进行搜索就可以了。思想很简单，代码写起来就是深度优先搜索和广度优先搜索那一套，代码实现起来也比较模式化，注意下边界条件就可以.
void DFS(vector<int> &candidates, vector<int> elements, int target, int pos)
{
if(target == 0)
{
ret.push_back(elements);
return;
}
if(pos==candidates.size() || target<0)
return;
DFS(candidates, elements, target, pos+1);
elements.push_back(candidates[pos]);
DFS(candidates, elements, target-candidates[pos], pos+1);
elements.pop_back();
}
但是这个代码是不是没有问题了呢？考虑一种情况A[]={1,1,6,1}, K=8。则上面的代码返回{1,1,6}, {1,6,1}, {1,6,1}，不要问为什么，人工测试一下就明白了。下面对代码进行了一点优化。现在比较流行微创新，其实一点点小的改进往往是程序中最关键的地方。
void DFS(vector<int> &candidates, vector<int> elements, int target, int pos)
{
if(target == 0)
{
ret.push_back(elements);
return;
}
if(pos==candidates.size() || target<0)
return;
int same=1;
for(size_t i=pos+1; i<candidates.size() && candidates[pos]==candidates[i]; i++,same++)
;
for(int i=0; i<same; i++)
{
for(int j=0; j<i; j++)
elements.push_back(candidates[pos]);
DFS(candidates, elements, target-candidates[pos]*i, pos+same);
for(int j=0; j<i; j++)
elements.pop_back();
}
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target){
vector<int> elements;
sort(candidates.begin(), candidates.end());
DFS(candidates, elements, target, 0);
return ret;
}
给定整数数组，元素各不相同，并且每个元素使用多次，其他条件和要求不变。仿照上面的代码框架很快就可以写出下面的代码来了。
void DFS(vector<int> &candidates, vector<int> elements, int target, int pos)
{
if(target == 0)
{
ret.push_back(elements);
return;
}
if(pos==candidates.size())
return;
for(int i=0; candidates[pos]*i<=target; i++)
{
for(int j=0; j<i; j++)
elements.push_back(candidates[pos]);
DFS(candidates, elements, target-candidates[pos]*i, pos+1);
for(int j=0; j<i; j++)
elements.pop_back();
}
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target){
vector<int> elements;
sort(candidates.begin(), candidates.end());
DFS(candidates, elements, target, 0);
return ret;
}
仔细分析一下上面的问题，如果数组大小为N，那么状态数就是2^N，复杂度高达O(2^N)。搜索我们基本可以不考虑了。这时候另外一种重要的方法开始登场了，对，就是动态规划，关于动态规划，这里就不介绍了。我们这里只针对具体的问题，从问题中分析出不变的东西。废话不多说，下面如何分析这个问题。为了方便的分析问题，集中到核心问题上来，我们不要求返回具体元素，只需要返回true或false。这里假定大家都了解了动态规划的基本的知识，如果不清楚，建议学习《算法导论》上关于动态规划的讲解。动态规划中，最重要的是最优子结构的证明和状态转移方程的推导。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。对于本题，我们作如下定义：dp[i+1][j]==（数组A[0…i]可以表示出j？）。也就是说如果能表示，则为true，否则为false。所以题目等价于求dp[n+1][K]，而dp[n+1][K]的求解取决于dp[n][K]和dp[n][K-A[n]]，这样就分解成子问题。状态转移方程也很简单：dp[i+1][j]=dp[i][j]|dp[i][j-A[i]]。最后还有一点要注意的是初始化！
bool combinationSum(int A[], int n, int K){
bool **dp = new bool* [n+1];
for(int i=0; i<=n; i++)
dp[i] = new bool [K+1];
//初始化
for(int i=0; i<=n; i++)
dp[i][0] = true;
for(int i=0; i<=n; i++)
{
for(int j=1; j<=K; j++)
dp[i][j] = false;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=K; j++){
dp[i][j] = j-A[i-1]>0 ? (dp[i-1][j]|dp[i-1][j-A[i-1]]) : dp[i-1][j];
}
}
bool ret = dp[n][K];
for(int i=0; i<n; i++)
delete [] dp[i];
delete [] dp;
return ret;
}
Read full article from Don't Panic! » 关于部分数组固定和的一类问题解析
前面写过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)，值得注意的是，此时并没有数组排序好的要求。
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从前到尾遍历的）。看下代码就都明白了。
/用map实现桶排序
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;
}
问题三、问题二的变体，当追求的和不是0而是target的时候怎么办？前面的思路都是一样，后面的怎么处理呢？前面提到桶排序，则我们可以在桶上直接来求。比如对于buck[i]就是表示和为i的sum区间，则只要考查buck[i-target]和buck[i+target]就行了。处理的时候，我们可以从一个确界开始，比如下界就考察buck[i]和buck[i+target]，上界就考察buck[i]和buck[i-target]。
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;
}
问题四、输入数组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整除。另外，任何一个整数的乘法因子都是素数。（如果不是素数，则可以继续分解）。下面看一个替换后的处理代码，替换的代码就不上了。
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表示数组里有多少个不同的素数。另外还应该考虑到数的溢出问题，对于有些语言可能就需要自己构造大数类了。
关于部分数组固定和的一类问题解析续
给定整数数组A[1…n]，判断是否可以从中选出若干个数，使它们的和恰好为K。比如A[]={1,2,4,7}，K=13。应该返回2,4,7。
先介绍一种简单的方法：状态搜索，对于数组A[]中的元素只有两种可能：选或者不选。所以我们可以得到下面这张图，然后对这张图进行搜索就可以了。思想很简单，代码写起来就是深度优先搜索和广度优先搜索那一套，代码实现起来也比较模式化，注意下边界条件就可以.
void DFS(vector<int> &candidates, vector<int> elements, int target, int pos)
{
if(target == 0)
{
ret.push_back(elements);
return;
}
if(pos==candidates.size() || target<0)
return;
DFS(candidates, elements, target, pos+1);
elements.push_back(candidates[pos]);
DFS(candidates, elements, target-candidates[pos], pos+1);
elements.pop_back();
}
但是这个代码是不是没有问题了呢？考虑一种情况A[]={1,1,6,1}, K=8。则上面的代码返回{1,1,6}, {1,6,1}, {1,6,1}，不要问为什么，人工测试一下就明白了。下面对代码进行了一点优化。现在比较流行微创新，其实一点点小的改进往往是程序中最关键的地方。
void DFS(vector<int> &candidates, vector<int> elements, int target, int pos)
{
if(target == 0)
{
ret.push_back(elements);
return;
}
if(pos==candidates.size() || target<0)
return;
int same=1;
for(size_t i=pos+1; i<candidates.size() && candidates[pos]==candidates[i]; i++,same++)
;
for(int i=0; i<same; i++)
{
for(int j=0; j<i; j++)
elements.push_back(candidates[pos]);
DFS(candidates, elements, target-candidates[pos]*i, pos+same);
for(int j=0; j<i; j++)
elements.pop_back();
}
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target){
vector<int> elements;
sort(candidates.begin(), candidates.end());
DFS(candidates, elements, target, 0);
return ret;
}
给定整数数组，元素各不相同，并且每个元素使用多次，其他条件和要求不变。仿照上面的代码框架很快就可以写出下面的代码来了。
void DFS(vector<int> &candidates, vector<int> elements, int target, int pos)
{
if(target == 0)
{
ret.push_back(elements);
return;
}
if(pos==candidates.size())
return;
for(int i=0; candidates[pos]*i<=target; i++)
{
for(int j=0; j<i; j++)
elements.push_back(candidates[pos]);
DFS(candidates, elements, target-candidates[pos]*i, pos+1);
for(int j=0; j<i; j++)
elements.pop_back();
}
}
vector<vector<int> > combinationSum(vector<int> &candidates, int target){
vector<int> elements;
sort(candidates.begin(), candidates.end());
DFS(candidates, elements, target, 0);
return ret;
}
仔细分析一下上面的问题，如果数组大小为N，那么状态数就是2^N，复杂度高达O(2^N)。搜索我们基本可以不考虑了。这时候另外一种重要的方法开始登场了，对，就是动态规划，关于动态规划，这里就不介绍了。我们这里只针对具体的问题，从问题中分析出不变的东西。废话不多说，下面如何分析这个问题。为了方便的分析问题，集中到核心问题上来，我们不要求返回具体元素，只需要返回true或false。这里假定大家都了解了动态规划的基本的知识，如果不清楚，建议学习《算法导论》上关于动态规划的讲解。动态规划中，最重要的是最优子结构的证明和状态转移方程的推导。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。对于本题，我们作如下定义：dp[i+1][j]==（数组A[0…i]可以表示出j？）。也就是说如果能表示，则为true，否则为false。所以题目等价于求dp[n+1][K]，而dp[n+1][K]的求解取决于dp[n][K]和dp[n][K-A[n]]，这样就分解成子问题。状态转移方程也很简单：dp[i+1][j]=dp[i][j]|dp[i][j-A[i]]。最后还有一点要注意的是初始化！
bool combinationSum(int A[], int n, int K){
bool **dp = new bool* [n+1];
for(int i=0; i<=n; i++)
dp[i] = new bool [K+1];
//初始化
for(int i=0; i<=n; i++)
dp[i][0] = true;
for(int i=0; i<=n; i++)
{
for(int j=1; j<=K; j++)
dp[i][j] = false;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=K; j++){
dp[i][j] = j-A[i-1]>0 ? (dp[i-1][j]|dp[i-1][j-A[i-1]]) : dp[i-1][j];
}
}
bool ret = dp[n][K];
for(int i=0; i<n; i++)
delete [] dp[i];
delete [] dp;
return ret;
}
Read full article from Don't Panic! » 关于部分数组固定和的一类问题解析
