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
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
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
thanks @ffao :)