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.     int longest = INT_MIN;
  20.     int shortest = INT_MAX;
  21.  
  22.     for(int i = 0; i < a.size(); i++) {
  23.  
  24.         sum += a[i];
  25.         int ques = sum - k;
  26.  
  27.         // Longest subarray
  28.         if(first.find(ques) != first.end()) {
  29.             int len = i - first[ques];
  30.             longest = max(longest, len);
  31.         }
  32.  
  33.         // Shortest subarray
  34.         if(last.find(ques) != last.end()) {
  35.             int len = i - last[ques];
  36.             shortest = min(shortest, len);
  37.         }
  38.  
  39.         // Store first occurrence
  40.         if(first.find(sum) == first.end())
  41.             first[sum] = i;
  42.  
  43.         // Store last occurrence
  44.         last[sum] = i;
  45.     }
  46.  
  47.     if(longest == INT_MIN)
  48.         cout << "No subarray found";
  49.     else {
  50.         cout << "Longest Length = " << longest << endl;
  51.         cout << "Shortest Length = " << shortest << endl;
  52.     }
  53.  
  54.     return 0;
  55. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Longest Length = 2
Shortest Length = 1
https://ideone.com/S2zRvH
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!