fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main() {
  6.     vector<int> arr = {2,2,3,5,2,2,3,2,2,1};
  7.  
  8.     int k = 8;
  9.     int n = arr.size();
  10.  
  11.     // prefix sum -> {first index, last index}
  12.     unordered_map<int, pair<int, int>> mp;
  13.  
  14.     int lrg = 0;
  15.     int sml = INT_MAX;
  16.  
  17.     // prefix sum array
  18.     vector<int> p(n, 0);
  19.  
  20.     p[0] = arr[0];
  21.  
  22.     for(int i = 1; i < arr.size(); i++) {
  23.         p[i] = p[i-1] + arr[i];
  24.     }
  25.  
  26.     // prefix sum 0 exists before the array starts
  27.     mp[0] = {-1, -1};
  28.  
  29.     for(int j = 0; j < arr.size(); j++) {
  30.  
  31.         int d = p[j] - k;
  32.  
  33.         if(mp.find(d) != mp.end()) {
  34.  
  35.             // Largest -> use first/earliest index
  36.             int len = j - mp[d].first;
  37.             lrg = max(lrg, len);
  38.  
  39.             // Smallest -> use last/latest index
  40.             len = j - mp[d].second;
  41.             sml = min(sml, len);
  42.         }
  43.  
  44.         // First occurrence
  45.         if(mp.find(p[j]) == mp.end()) {
  46.             mp[p[j]] = {j, j};
  47.         }
  48.         else {
  49.             // Keep first index, update last index
  50.             mp[p[j]].second = j;
  51.         }
  52.     }
  53.  
  54.     cout << "Largest length: " << lrg << endl;
  55.     cout << "Smallest length: " << sml << endl;
  56.  
  57.     return 0;
  58. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Largest length: 4
Smallest length: 2
https://ideone.com/3f8GCV
language:
C++14 (gcc 8.3)
created:
3 hours 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!