请教一个求数组部分和的是否等于某数的算法

fsilence

假如有一个数组A，数组元素个数为SIZEA，现在给你一个整数M，求一个最小整数k，使得k个数组元素之和等于M，注意这里要保证k最小，如果不存在这样的k返回-1。

skygram

　　将数组Ａ排序，设为升序．

　　接下来好办了吧，遍历相加，如果相等或大于就跳出就好了

ArXoR

用hash表,
扫描一遍数组
到Ai时,计算到此位置时的部分和Si,
在hash表里查询Si-M
然后把(Si,i)插入hash表
扫描完找到最小k就结束了

hash表里对于Si相同的节点,保存更新的位置

O(n)的复杂度和空间复杂度

[ 本帖最后由 ArXoR 于 2006-2-14 20:57 编辑 ]

fsilence

2楼的算法不对，遍历相加的情况是不全面的，也可能排序后的结果是A[1]和某个A[i]加和刚好是M
3楼的算法我没看懂

ArXoR

就是对于每个Ai我们都希望判定它是不是一个和为M的子串的尾部
而如果知道到Ai为止的部分和Si,那就是看之前是否存在Sj=Si-M,这个用hash最好
而我们总是希望找最大的j,这样我们只要记录有序对(Sx,y),y是当前得到的Sx的最后的位置
应该就是这样了吧

yzc2002

对于序列A1,A2,A3...以及一个预设的和M,对于某个值An,假设:
S=A_i+...+A_n-1 <= M(若i不存在,则认为i=n, S=0)
则令S=S+A_n,其值有三种可能:
(1)S<M,则继续下一个值,累加入S
(2)S>M,则减去A_i, A_i+1...直至S<=M为止
(3)S=M,则得到一个连续和为M的子列,与到目前为止,最短的连续串(长度设为min_k)相比,以得到的min_k
最后就得到了和为M的最短连续子列

1. int sub_sum(int *array, int n, int m, int *start)
   
2. {
   
3.     int s=0, min_k=n+1, i, begin=0;
   
4.     for(i=0; i<n; i++) {
   
5.         s += array[i];
   
6.         while(s > m)  s -= array[begin++];
   
7.         if(s == m && i-begin+1 < min_k) {
   
8.             min_k = i-begin+1;
   
9.             *start = begin;
   
10.         }
    
11.     }
    
12.     return min_k;
    
13. }

复制代码

[ 本帖最后由 yzc2002 于 2006-2-15 11:23 编辑 ]

yzc2002

sorry!没看清.
如果可以是不连续的话,则用动态规划
S(n,M)=min(S(n-1, M-An)+1, S(n-1, M))

ArXoR

原帖由 yzc2002 于 2/15/06 11:19 发表
对于序列A1,A2,A3...以及一个预设的和M,对于某个值An,假设:
S=A_i+...+A_n-1 <= M(若i不存在,则认为i=n, S=0)
则令S=S+A_n,其值有三种可能:
(1)S<M,则继续下一个值,累加入S
(2)S>M,则减去A_i, A_i+1 ...

如果我没理解错,要求全是非负数才能这样做吧?

openX

原帖由 fsilence 于 2006-2-14 19:27 发表
假如有一个数组A，数组元素个数为SIZEA，现在给你一个整数M，求一个最小整数k，使得k个数组元素之和等于M，注意这里要保证k最小，如果不存在这样的k返回-1。

1。先对a从大到小排序。
2。

1. 
   
2. int num = M;
   
3. 
   
4. int checkM()
   
5. {
   
6. int count = 0;
   
7. (for i=0; i<sizea; i++)
   
8. {
   
9.    num -= A[i];
   
10.    if(num > 0)
    
11.    {
    
12.       count++;
    
13.    }
    
14.    else if(num == 0)
    
15.   {
    
16.       count++;
    
17.       break;
    
18.    }
    
19.     else
    
20.     {
    
21.        return -1;
    
22.     }
    
23. }
    
24. 
    
25. return count;
    
26. }
    
27. 
    

复制代码

win_hate

原帖由 ArXoR 于 2006-2-14 20:53 发表
用hash表,
扫描一遍数组
到Ai时,计算到此位置时的部分和Si,
在hash表里查询Si-M
然后把(Si,i)插入hash表
扫描完找到最小k就结束了

hash表里对于Si相同的节点,保存更新的位置

O(n)的复杂度和空间复杂度

这种方法求出来的总是连续和，是吗？ 或者我理解错了。