Thursday, June 9, 2016

Leetcode: 327. Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Given nums = [-2, 5, -1]lower = -2upper = 2,
Return 3.
The three ranges are : [0, 0][2, 2][0, 2] and their respective sums are: -2, -1, 2.
Solution 1: Use Segment Tree

Solution 2: Use Binary Search Tree

No comments:

Post a Comment