fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. int countShortestSubarraysWithSumK(const vector<int>& nums, int k) {
  8.     unordered_map<int, int> seen; // prefix_sum -> earliest index
  9.     seen[0]=-1;int sum=0, min=INT_MAX,c=0;
  10.  
  11.     for (int i = 0; i < nums.size(); ++i) {
  12.     	sum+=nums[i];
  13.     	if (seen.find(sum - k) != seen.end()) {
  14.     		int x=i-seen[sum-k];
  15.     		if(x<min){ x=min; c=1;}
  16.     		else if(x==min) c++;
  17.  
  18.     	}
  19.     	 if (seen.find(sum) == seen.end()) {
  20.             seen[sum] = i;
  21.         }
  22.     }
  23.     return c;
  24. }
  25.  
  26. int main() {
  27.     vector<int> A = {10, 5, 2, 7, 1, 9, 8, 7};
  28.     int k = 15;
  29.  
  30.     int result = countShortestSubarraysWithSumK(A, k);
  31.     cout << "Count of shortest subarrays with sum = " << k << " is: " << result << endl;
  32.  
  33.     return 0;
  34. }
  35.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Count of shortest subarrays with sum = 15 is: 1
https://ideone.com/QLwgpb
language:
C++ (gcc 8.3)
created:
9 days 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!