fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <climits>
  5. using namespace std;
  6.  
  7. int main() {
  8.  
  9.     vector<int> a = {2,7,4,8,9,1,6};
  10.     int k = 9;
  11.  
  12.     unordered_map<int,int> first;
  13.     unordered_map<int,int> last;
  14.  
  15.     first[0] = -1;
  16.     last[0] = -1;
  17.  
  18.     int sum = 0;
  19.  
  20.     int longest = INT_MIN;
  21.     int shortest = INT_MAX;
  22.  
  23.     int maxCount = 0;
  24.     int minCount = 0;
  25.  
  26.     for(int i = 0; i < a.size(); i++) {
  27.  
  28.         sum += a[i];
  29.         int ques = sum - k;
  30.  
  31.         // Longest Subarray
  32.         if(first.find(ques) != first.end()) {
  33.  
  34.             int len = i - first[ques];
  35.  
  36.             if(len > longest) {
  37.                 longest = len;
  38.                 maxCount = 1;
  39.             }
  40.             else if(len == longest) {
  41.                 maxCount++;
  42.             }
  43.         }
  44.  
  45.         // Shortest Subarray
  46.         if(last.find(ques) != last.end()) {
  47.  
  48.             int len = i - last[ques];
  49.  
  50.             if(len < shortest) {
  51.                 shortest = len;
  52.                 minCount = 1;
  53.             }
  54.             else if(len == shortest) {
  55.                 minCount++;
  56.             }
  57.         }
  58.  
  59.         // Store first occurrence
  60.         if(first.find(sum) == first.end())
  61.             first[sum] = i;
  62.  
  63.         // Store last occurrence
  64.         last[sum] = i;
  65.     }
  66.  
  67.     if(longest == INT_MIN) {
  68.         cout << "No subarray found";
  69.     }
  70.     else {
  71.         cout << "Longest Length = " << longest << endl;
  72.         cout << "Number of Longest Subarrays = " << maxCount << endl;
  73.  
  74.         cout << "Shortest Length = " << shortest << endl;
  75.         cout << "Number of Shortest Subarrays = " << minCount << endl;
  76.     }
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Longest Length = 2
Number of Longest Subarrays = 1
Shortest Length = 1
Number of Shortest Subarrays = 1
https://ideone.com/PPtMze
language:
C++14 (gcc 8.3)
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!