fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. /* 
  4. 3 3
  5. 1 2 3
  6. output
  7. 2
  8.  
  9.  
  10. */
  11.  
  12. import java.util.*;
  13. import java.lang.*;
  14. import java.io.*;
  15.  
  16. /* Name of the class has to be "Main" only if the class is public. */
  17. class Ideone
  18. {
  19. 	public static void main (String[] args) throws java.lang.Exception
  20. 	{
  21.  
  22. 		Scanner sc = new Scanner(System.in);
  23. 		int n=sc.nextInt();
  24. 		int k=sc.nextInt();
  25. 		int nums[] = new int[n];
  26. 		for(int i=0; i<n; i++){
  27. 			nums[i]=sc.nextInt();
  28. 		}
  29.  
  30. 		int res = subarraySumBrureForce2(nums,k);
  31. 		System.out.println(res);
  32.  
  33. 	}
  34.  
  35. 	//lead to optimal solution
  36. 	public static int subarraySumBrureForce2(int[] nums, int k) {
  37.         // make a prefix arry
  38.         int psum =0,cnt=0;
  39.         int prefix[] = new int[nums.length+1];
  40.         prefix[0] = 0;
  41.         for(int i=1 ; i<=nums.length;i++){
  42.            prefix[i] =prefix[i-1]+ nums[i-1];
  43.         } 
  44.  
  45.         for(int i=1 ; i<prefix.length;i++){
  46.           int val = prefix[i] - k;
  47.           for(int j=0;j<i;j++){
  48.           	if(val == prefix[j]){
  49.           		cnt++;
  50.           	}
  51.           }
  52.         } 
  53.  
  54.         System.out.println(Arrays.toString(prefix));
  55.  
  56.         return cnt;
  57.     }
  58.  
  59. 	public static int subarraySum(int[] nums, int k) {
  60.         // make a prefix arry
  61.         int psum =0,cnt=0;
  62.         HashMap<Integer,Integer> map =new HashMap<>();
  63.         map.put(0,1);
  64.         for(int i=0 ; i<nums.length;i++){
  65.             psum+=nums[i];
  66.             if(map.containsKey(psum - k)){
  67.                 cnt+=map.get(psum - k);
  68.             }
  69.             map.put(psum,map.getOrDefault(psum,0)+1);
  70.         } 
  71.  
  72.  
  73.         return cnt;
  74.     }
  75. }
Success #stdin #stdout 0.11s 54492KB
comments (?)
stdin
copy 
6 3
1 0 1 2 10 8
stdout
copy 
[0, 1, 1, 2, 4, 14, 22]
2
https://ideone.com/XwaN1E
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!