Блог пользователя ChandraBhan

Find subarray from given array satisfying a particular condition.
Автор ChandraBhan, 9 лет назад, По-английски

Given an array and an integer T. We need to find a subarray from I, I + 1, I + 2……..j such that ||a [I] + a [I + 1] + ……. a [j] | – T| is minimum.? Element's can be negative .size of array<=1000000

Link to above problem

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

a[l] + ... + a[j] is equal to S[j + 1] - S[l] where S is the partial sum array S[i] = a[0] + ... + a[i - 1].

So calculate partial sum array, then sort it and use two pointer method to find two indices a, b such that S[b] - S[a] is as close to T as possible.

Calculating partial sum array is O(n), sorting is and two pointers is O(n), so the algorithm is .

EDIT: actual source

→ Ответить