Guest User

Two pointers

a guest
Oct 28th, 2016
677
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.44 KB | None | 0 0
  1. //количество подотрезков отсортированного массива с суммой <= S
  2. // длина массива = n
  3. int arr[N];
  4. int getCount() {
  5.     int left = 0;
  6.     int right = 0;
  7.     int curSum = 0;
  8.     int count = 0;
  9.     while (left < n) {     
  10.         while (right < n && curSum + arr[right] <= S) {
  11.             curSum += arr[right];
  12.             right++;
  13.         }
  14.         count += right - left;
  15.         curSum -= arr[left];
  16.         left++;
  17.     }
  18.     return count;
  19. }
Advertisement
Add Comment
Please, Sign In to add comment