顺序求和算法求教

Question

除了一个个顺序计算，有什么好办法快速知道一串数的顺序和是某个数,谢谢比如:以下数希望找到顺序求和能得到某个数，比如31(也可能是其他数)1
5
5
7
3
2
10
9
3
2某个结果:7+3+2+10+9=31目前的算法是:第1行
1+5否
1+5+5否
1+5+5+7否。。
换第2行
5+5否
5+5+7否

直到换至第4行
7+3否
7+3+2否

7+3+2+10+9找到这样太慢了，有好点的办法吗，谢谢！

Answer 1

          List<int> _i = new List<int>();
            _i.Add(1);
            _i.Add(5);
            _i.Add(5);
            _i.Add(7);
            _i.Add(3);
            _i.Add(2);
            _i.Add(10);
            _i.Add(9);
            _i.Add(3);
            _i.Add(2);
            for (int i = 0; i < _i.Count; i++)
            {
                int sum = _i[i];
                for (int j = i + 1; j < _i.Count; j++)
                {
                    sum += +_i[j];
                    if (sum == 31)
                    {
                        Console.WriteLine("结果：");
                        for (int num = i; num <= j; num++)
                        {
                            Console.WriteLine("{0}", _i[num].ToString());
                        }
                        break;
                    }
                    else
                    {
                        Console.WriteLine("木有找到");
                    }
                }            }
            /*
             结果：
            7
            3
            2
            10
            9
            */

Answer 2

循环历遍吧.
因为lz没有定规则:
1.31必须拆分成是不等的数相加的和.
2.数组必须是不重复元素.如果31可以任意拆分,数组可以是任意元素.也就只有循环历遍相加来确定了.我举个极端例子.
这个数组是 1000个 1(有顺序)组成,那么其中的31个数任意组合成 31 的 组合数有多少个? 
组合问题 C31-1000必须历遍是才能得出来
(数组过大的时候,历遍都会历遍死)

Answer 3

刚才用sql写了下，结果31蛮容易的，就是筛选出哪几个之和是31就有点困了，想了一会
--> 测试数据：[TB]
if object_id('[TB]') is not null drop table [TB]
create table [TB](id int identity(1,1),[col] int)
insert [TB]
select 1 union all
select 5 union all
select 5 union all
select 7 union all
select 3 union all
select 2 union all
select 10 union all
select 9 union all
select 3 union all
select 2declare @i int
set @i=31select A.* 
from (
select num=rtrim(id)+'.'+rtrim(number)+'.'+rtrim((select sum(col) from TB where id<=t.id and id>number))+'.'+'0' from [TB] t,master..spt_values 
where type='p' and number<(select max(id) from TB)
) as B ,TB A 
where charindex(rtrim(@i)+'.',num)>0 
and A.id<=cast(parsename(num,4) as int)
and A.id>cast(parsename(num,3) as int)/*
id          col
----------- -----------
4           7
5           3
6           2
7           10
8           9(5 行受影响)*/drop table TB

Answer 4

这个就是最大字段和，
baidu这个就可以了

Answer 5

最大字段和static void Main(string[] args)
        {
            List<int> _i = new List<int>();
            _i.Add(1);
            _i.Add(5);
            _i.Add(5);
            _i.Add(7);
            _i.Add(3);
            _i.Add(2);
            _i.Add(10);
            _i.Add(9);
            _i.Add(3);
            _i.Add(2);            int sum = 0;            int b = 0;            for (int i = 0; i < _i.Count; i++)
            {                if (b > 0) b += _i[i];                else b = _i[i];                if (b > sum) sum = b;            }            Console.WriteLine(sum);
        }貌似和楼主的要求不符合哦

Answer 6

用一重循环O(n)应该可以，配合一个累加就行。
using System;namespace csdnTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] items = new int[] { 1, 5, 5, 7, 3, 2, 10, 9, 3, 2 };
            int[] acc = new int[items.Length + 1];
            int j = 0, sum = 31;            for (int i = 0; i < items.Length; i++)
            {
                acc[i + 1] = acc[i] + items[i];
                while (acc[i + 1] - acc[j] > sum)
                    j++;                //输出结果,有多组解应该也可以,相比之下输出部分效率最低,LZ可自行优化
                if (acc[i + 1] - acc[j] == sum)
                {
                    for (int k = j; k <= i; k++)
                        Console.Write("{0} ", items[k]);
                    Console.WriteLine("= {0}", sum);
                }
            }            Console.ReadKey();
        }
    }
}

Answer 7

刚想到一个问题，如果有负数的话，上面的方法稍微有些问题，不过有n*log(n)的方法，
同样是先计算出累加数组，然后对该数组排个序，然后同样用双指针的方法找出差为sum的所有序列(例子中是31)，然后判断一下后面的序列的位置是否大于前面的序列，如果大于则输出，否则舍弃。
复杂度最高的部分就是排序，n*log(n)