Count of Range Sum这道题都读不懂题……

刚刚放出来的这个题目，到底是什么意思啊，完全看不懂要哭了……
https://leetcode.com/problems/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.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

楼主莫慌，题是我出的，可能是我英语太差了

题意很简单，就是给你一个数组，求数组的所有子数组和(sub array sum)在区间[lower, upper]之内的个数

题解我blog上有~，用的Merge Sort，边排序边数出来

抛砖引玉

1.     public class Solution {
   
2.         SegmentTreeNode root = null;
   
3. 
   
4.         public SegmentTreeNode buildTree(long[] nums, int left, int right) {
   
5.             if (left > right) return null;
   
6. 
   
7.             SegmentTreeNode p = new SegmentTreeNode(nums[left], nums[right]);
   
8.             if (left == right) return p;
   
9. 
   
10.             int mid = left + (right - left) / 2;
    
11.             p.left = buildTree(nums, left, mid);
    
12.             p.right = buildTree(nums, mid + 1, right);
    
13.             return p;
    
14.         }
    
15. 
    
16.         public void update(SegmentTreeNode node, long key) {
    
17.             if (node != null && node.start <= key && node.end >= key) {
    
18.                 node.val++;
    
19.                 update(node.left, key);
    
20.                 update(node.right, key);
    
21.             }
    
22.         }
    
23. 
    
24.         public int count(SegmentTreeNode node, long low, long high) {
    
25.             if (node == null || node.start > high || node.end < low) return 0;
    
26.             if (node.start >= low && node.end <= high) return node.val;
    
27.             return count(node.left, low, high) + count(node.right, low, high);
    
28.         }
    
29. 
    
30.         public int countRangeSum(int[] nums, int lower, int upper) {
    
31.             int rslt = 0;
    
32.             int n = nums.length;
    
33.             if (n <= 0) return rslt;
    
34. 
    
35.             long[] sum_array = new long[n];
    
36.             sum_array[0] = nums[0];
    
37.             for (int i = 1; i < n; i++) {
    
38.                 sum_array[i] = nums[i] + sum_array[i - 1];
    
39.             }
    
40.             long sum = sum_array[n - 1];
    
41.             Arrays.sort(sum_array);
    
42.             int unique = 1;
    
43.             for (int j=1; j<n; j++ ) {
    
44.                 if (sum_array[j] != sum_array[j-1]) {
    
45.                     sum_array[unique] = sum_array[j];
    
46.                     unique++;
    
47.                 }
    
48.             }
    
49.             root = buildTree(sum_array, 0, unique - 1);
    
50. 
    
51.             for (int i = n - 1; i >= 0; i--) {
    
52.                 update(root, sum);
    
53.                 sum -= nums[i];
    
54.                 rslt += count(root, lower + sum, upper + sum);
    
55.             }
    
56. 
    
57.             return rslt;
    
58.         }
    
59. 
    
60.         public class SegmentTreeNode {
    
61.             int val;
    
62.             long start;
    
63.             long end;
    
64.             SegmentTreeNode left;
    
65.             SegmentTreeNode right;
    
66. 
    
67.             public SegmentTreeNode(long start, long end) {
    
68.                 this.val = 0;
    
69.                 this.start = start;
    
70.                 this.end = end;
    
71.                 this.left = null;
    
72.                 this.right = null;
    
73.             }
    
74.         }
    
75.     }

复制代码

关于 Fenwick Tree， 推荐大家看一下这篇介绍：
http://www.hrwhisper.me/binary-indexed-tree-fenwick-tree/

严格来说这不是个 “Tree”， 是一个树状的数组，index之间的移动的关系主要是根据最低位的1来定的，这个数据结构简洁巧妙。适合处理range类的问题。

求有多少个连续区间，满足，区间内的数的和大于等于lower，并且小于等于upper

Let's see the example first:
[-2,5,-1], and its indices i, j should meet the requirement: i<= j, then we could get the following sequences:
[0,0],[0,1],[0,2],[1,1],[1,2],[2,2].
Notice that sum(i,j) is defined as the sum of the elements in the array between i and j, so write down each result in the above interval:
[0,0]=-2
[0,1]=3
[0,2]=2
[1,1]=5
[1,2]=4
[2,2]=-1
Then we should count the total numbers of range which should locate between lower and upper, here we use lower=-2 and upper=2, count the above numbers that meet this requirement, and we get 3 finally(-2, -1, 2)

I can understand the meaning of title, but I still can not work it out. What a shame

我感觉可以用Fenwick Tree做，或者线段树，或者带node count的BST。不知道有没有其他更巧妙的解法？
大概方法是这样：首先用dp计算 sum(0, i)，这个是 O(n)
然后对于一个index j，关键就是想知道选择哪些 i 能够使得 sum(0,j) - sum(0, i-1)落在给定的range内
这等价于求之前的sum(0, i-1)落在某个range内的那些i，
可以用Fenwick Tree转化成求count的问题。最终复杂度就是 O(n log (n))了

Fenwick Tree 已过。不过leetcode又来了一个恶心的test case，里面有 -2147483648 这种东西。。我用int的时候又over flow了。。改成long才pass的。

163 发表于 2016-1-11 05:25
Fenwick Tree 已过。不过leetcode又来了一个恶心的test case，里面有 -2147483648 这种东西。。我用int的时 ...

厉害！厉害！学习了

就是求区间和, 然后最后和要在那个要求区间内.