未排序数组中累加和为给定值的系列问题

题目一：Zero Sum Subarray

给定一整形数组，返回序列和为0的子数组的起始和结束下标。

比如：int[] array={-3,1,2,-3,4};   返回（0,2）和（1,3）。

题解：使用hashmap保存数组中从0开始到索引i的子段和，在将值push进map之前，先检查map中是否已经存在，

若存在则表示找到一组。

注意：map中的键值对key表示cursum，而value应表示在index之前的sum为多少。这是为了能成功返回第一组（0,2），

所以事先先将（0,0）的键值对put进map中，则当index=2时，才能找到（0,2）这个满足要求的子数组！！！

//zero sum subarray
    public void subarraySum(int[] data)
    {
    	HashMap<Integer,Integer> map=new HashMap();
    	map.put(0, 0);//necessary~
    	int cursum=0;
    	for(int i=0;i<data.length;i++)
    	{
    		cursum+=data[i];
    		if(map.containsKey(cursum))
    		{
    			System.out.println("下标："+map.get(cursum)+"到"+i);
    		}
    			map.put(cursum,i+1);//i+1之前的子段和为cursum;
    	}
    }

      但是该例程若在（0,2）的和为0，且（3,5）的和为零时，那么（0,5）的和也为0，但是结果没有给出。

题目二：Subarray Sum Closest

给定一个整型数组，找到和最接近0的子序列。

返回该子数组的起始和结束下标。

比如：Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].

解析：因要求的子串和不固定，所以不适合再用哈希表的方法，使用排序可在O（n*logn）内解决。

具体步骤：

1.首先遍历一遍数组求的子串和；

2.对子串和排序；

3.逐个比较相邻两项差值的绝对值，返回差值绝对值最小的两项。

这种方法的时间复杂度主要集中在排序上，由于除了记录子串和之外，还需记录索引，故引入pair类。最后排序时先按照sum值先排序，再按照索引值排序。

import java.util.*;
public class TestClass {
    public static void main(String args[]) {
	  TestClass test=new TestClass();

			int[] array={-3,1,1,-3,5};
			Result res=test.subarraySumClosest(array);
			System.out.println(""+res.begin+" "+res.end);
    }
//sum subarray closest
    public Result subarraySumClosest(int[] data)
    {
    	if(data == null||data.length <= 1)
    		return new Result(0,0);
    	Pair[] array=new Pair[data.length+1];//array的长度为data.length+1
    	array[0]=new Pair(0,0);//array[0]表示data[0]之前的和，设为0；
    	       //类似链表中dummy头结点的做法，避免了对单个子串和是否为最小情况的单独考虑；
    	int cursum=0;
    	for(int i=1;i<=data.length;i++)
    	{
    		cursum+=data[i-1];
    		array[i]=new Pair(cursum,i);
    	}
    	//对array按规则排序
    	Arrays.sort(array,new Comparator<Pair>(){
    		public int compare(Pair a,Pair b)//先按sum排序
    		{
    				return a.sum-b.sum;
    		}
    	});
    	int min_subsum=Integer.MAX_VALUE;
    	int closest_p=1;
    	for(int i=1;i<array.length;i++)
    	{
    		if(array[i].sum-array[i-1].sum < min_subsum)
    		{
    			min_subsum=array[i].sum-array[i-1].sum;
    			closest_p=i;
    		}
    	}
    	//排序后大的index可能排在了小的index的前面；
    	int begin=Math.min(array[closest_p].index, array[closest_p-1].index);
    	int end=Math.max(array[closest_p].index, array[closest_p-1].index)-1;// end要减去1；
    	Result result=new Result(begin,end);
    	return result;
    }
       
    class Pair
    {
    	int sum;//sum存放数组当前下标之前的前缀数组和！！！
    	int index;//index存放数组下标
    	public Pair(int sum,int index)
    	{
    		this.sum=sum;
    		this.index=index;
    	}
    }
    class Result
    {
    	int begin;
    	int end;
    	public Result(int begin,int end)
    	{
    		this.begin=begin;
    		this.end=end;
    	}
    }
}

题目三：

给定一个无序数组，其中元素可正，可负，可0，给定一个整数k。求array所有子数组中累加和为k的最长子数组长度。

变型题目：

1 。数组中元素可正，可负，可0，求所有子数组中正数与负数个数相等的最大子数组长度

2 。数组中元素只有1或0，求所有子数组中1和0个数相等的最长子数组长度

原问题代码如下：仍利用Zero Sum Subarray的方法，map中只记录一个累加和最早出现的位置。

 public int getMaxLength(int[] array,int k)
   {
	   if(array == null||array.length == 0)
		   return 0;
	   int len=0;
	   int cursum=0;
	   HashMap<Integer,Integer> map=new HashMap();
	   map.put(0,0);//0之前的累加和为0;
	   for(int i=0;i<array.length;i++)
	   {
		  cursum+=array[i];
		 if(map.containsKey(cursum-k))
		 {
			 len=Math.max(len, i-map.get(cursum-k)+1);
		 }
		 if(!map.containsKey(cursum))
		 {
			 map.put(cursum,i+1);//i+1之前的累加和为cursum且cursum第一次出现；
		 }
	   }
	   return len;
 }

第一个补充问题，先把正数全部变为1，负数变为-1，0不变，求累加和为0的最长子数组长度即可；

第二个补充问题，把0全部变为-1,1不变，求累加和为0的最长子数组长度即可。