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

c#算法面试题,高手的请来
请找出一个数组中连续相加为0的起始、结束索引。如数组[3,-2, 1,1,-2,4]中结果是索引1至3、索引2至4。(请考虑时间复杂度,如实现O(n)可另加30分)(20分)

------解决方案--------------------
闲来无事写了个玩玩

C# code
    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 });
                
            }

        }

    }