c#算法面试题,高手的请来

Question

请找出一个数组中连续相加为0的起始、结束索引。如数组[3，-2， 1，1，-2，4]中结果是索引1至3、索引2至4。（请考虑时间复杂度，如实现O(n)可另加30分）（20分）

Answer 1

先数据变换一下变成矢量数据，那么他会形成一个波形图[3，-2， 1，1，-2，4]
变换成[3,1,2,3,1,5]现在看出规律来了把，如果放在波形图上解释，就是不管你中间怎么跳，最终回到原位了，所以那中间的玩意和值为0（当然这里点小bug需要在程序里排除，那就是他根本就是一条直线 或者两个点直接没有其它点）东西就这么玩，代码就不写了，很容易搞定，只要注意上面的小bug，两次扫秒即可。可以算

Answer 2

闲来无事写了个玩玩    private void button1_Click(object sender, EventArgs e)
        {
            Hashtable temp = new Hashtable();
            int[] init_Array = new int[] { 3, -2, 1, 1, -2, 4 };
            int j = 0;
            for (int i = 0; i < init_Array.Length; i++)
            {
                
                j = init_Array[i] + j;                p_point p = temp[j] == null ? new p_point() : p = (p_point)temp[j];
                
                
                p.setNewIndex(i);
                temp[j] = p;
                
            }
 
            string res_str = String.Empty;
            foreach (var item in temp.Values)
            {
                string str = "索引{0}-索引{1}的连续和为0 \n";
                var t = (p_point)item;                var list = t.tempobj;
               
                for (int i = 0; i < list.Count - 1; i++)
                {
                    for (int jj = i + 1; jj < list.Count; jj++)
                    {
                        //判定两点间没有数据以及所有点都在一条直线上
                        if ( CheckIsNotLine(list[i].pot_index, list[jj].pot_index,init_Array))
                        {
                            res_str += String.Format(str, list[i].pot_index + 1, list[jj].pot_index);
                        }
                        
                        
                    }                }
            }
            MessageBox.Show(res_str);        }        private bool CheckIsNotLine(int start,int end,int[] array)
        {
                  return    ! (array.Skip(start - 1).Take(end - start).Sum() == 2 * array[start]);
          
        }        
        class resobj
        {
            public int pot_index { get; set; }        }        class p_point
        {            public p_point()
            {
                tempobj = new List<resobj>();            }
            public List<resobj> tempobj { get; set; }
            public void setNewIndex(int index)
            {
                tempobj.Add(new resobj() { pot_index = index });
                
            }        }    }

Answer 3

那只能是设I，J  分别扫描整个数组
 for (int i=0 to  i<length  i++)
{
   sum=varr[i]; 
   for (int j=i+1 to j<length   j++)
   {
         sum+=varr[j];
         if (sum==0)
            //提取起始点I， 最后一个点J
   }
   sum=0;
}}         ...........
........
...

Answer 4

public static class D
{
public static int sum = 0;
public static bool addSumIsZero(int value)
{
sum+=value;
if(sum==0)
{
return true;
}
return false;
}
}int[] arr = new int[] { 3, -2, -1, 1, -2, 4 };
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.Length; i++)
{
if (D.addSumIsZero(arr[i]))
{
sb.AppendLine("第" + i.ToString() + "个元素，" + "当前值" + arr[i].ToString() + " 之和为0");
}
}
MessageBox.Show(sb.ToString(), "提示");

Answer 5

O(N^2)很容易
O((N-1)^2/2) 也容易
O(NlogN) 也行
O(N)....没想到

Answer 6

O((N-1)^2/2)==O(N^2),O（）是用来比较无穷大量的阶数的符号，具体可以参阅随便一本数学分析的书