Given an integer array
nums, return the number of range sums that lie in
[lower, upper] inclusive.
S(i, j) is defined as the sum of the elements in
nums between indices
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Given nums =
[-2, 5, -1], lower =
-2, upper =
The three ranges are :
[0, 2] and their respective sums are:
-2, -1, 2.
Special thanks to @dietpepsi for adding this problem and creating all test cases.