日期:2014-05-18  浏览次数:20836 次

一个算法问题求帮助

请找出一个数组中连续相加为0的起始、结束索引。如数组[3,-2, 1,1,-2,4]中结果是索引1至3、索引2至4。(请考虑时间

复杂度,实现O(n)

------解决方案--------------------
O(n)....没可能吧
------解决方案--------------------
循环相加判断,只供参考
------解决方案--------------------
C# code
List<string> record_index = new List<string>();
                int[] compute_array = new int[] {3,-2, 1,1,-2,4 };
                for (int i = 0; i < compute_array.Count(); i++)
                {
                    int sum = compute_array[i];
                    for (int pos = i + 1; pos < compute_array.Count(); pos++)
                    {
                        sum += compute_array[pos];
                        if (sum != 0)
                            continue;
                        else
                        {
                            record_index.Add(i.ToString()+"|"+pos.ToString());
                            break;
                        }
                        
                    }

                }
                /*
                 * 1|3
                 * 2|4
                 */

------解决方案--------------------
3楼说的方法不行么?
------解决方案--------------------
访问方法
------解决方案--------------------
这个你想要的?

C# code

int[] ilist = new int[6] { -1, 3, -2, 10, -10, 2 };
        private void button1_Click(object sender, EventArgs e)
        {

            ArrayList aa = GetStartEnd(0, new ArrayList());


            foreach (MyList myl in aa)
            {
                MessageBox.Show(myl.startpoint.ToString()+","+myl.endpoint.ToString());
            }
        }


        ArrayList GetStartEnd(int startIndex, ArrayList list)
        {
            int summary = 0;
            for (int i = startIndex; i < ilist.Length; i++)
            {
                summary += ilist[i];
                if (i != ilist.Length - 1)
                {
                    if (summary == 0)
                    {
                        list.Add(new MyList(startIndex, i));
                    }
                }
                else
                {
                    if (summary == 0)
                    {
                        list.Add(new MyList(startIndex, i));
                    }
                    GetStartEnd(startIndex+1, list);
                    break;
                }
            }
            return list;
        }


public class MyList
    {
        public int startpoint;
        public int endpoint;

        public MyList(int s, int e)
        {
            startpoint = s;
            endpoint = e;
        }
    }