【算法题】- 求和等于K子数组

一整数（有正有负）数组，用尽量少的时间计算数组中和为某个整数的所有子数组

 1 public class SumK {
 2 
 3     public static void main(String[] args) {
 4         
 5         int[] array = {4,5,2,4,7,1,8,-3,6,3,2,6,1,4,-6,7,-4,2,-1,8,5,2,7,4,3};
 6         int k = 11;
 7         Map<Integer,Integer> set = new HashMap<Integer,Integer>();
 8         int[] sum = new int[array.length];
 9         sum[0]=array[0];
10         set.put(sum[0], 0);
11         for(int i =1 ; i < array.length ;i++){
12             sum[i]=sum[i-1]+array[i];
13             set.put(sum[i],i);
14         }
15         int count = 1;
16         for(int i=array.length-1;i>0;i--){
17             int key = sum[i]-k;
18             if(set.get(key) != null && set.get(key) != 0){
19                 System.out.print("第"+count+++"组字串 ");
20                 for(int j = set.get(key)+1 ; j <=i ;j++){
21                     System.out.print(array[j]+" ");
22                 }
23                 System.out.println();
24             }
25         }
26     }
27 }

思路是把子数组的和转化成前缀数组之间的差等于K，然后从后遍历。