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

dietpepsi 发表于 2016-1-15 11:05
blog是用wordpress啊
主题抄的hrwhisper，叫dazzling

嘿嘿，今天本来想换个主题，看到大家觉得dazzling主题不错就不换了

hrwhisper 发表于 2016-1-18 08:05
嘿嘿，今天本来想换个主题，看到大家觉得dazzling主题不错就不换了

确实是很好的主题，干净整洁，绿色环保

膜拜各路大神，在discussion区对大神的ID真是熟读于心了 好好

这个题好难啊。。。

这个题目我真的也没看懂。。。。。

借地求助一下代码问题……下面是我第一遍刷题的时候，最后看了答案写的code但是现在看不大懂了。

主要就是终止条件的地方。因为那个helper function就是数[left,right]内有多少符合条件的range，于是到最后如果 left==right，说明range内只有一个数，这样不应该比较这个数和lower还有upper的关系吗？为什么比较的是rangeSum[left]呢，这个是[0,left]的和呀……这样就把这个range数进来了，而不是[left,right]这个range了……

但是这个code还可以过OJ……

leetcode discuss里也有不少是这样写的，但是都没解释……
各路大神帮忙看一下……谢谢！！！

1.     vector<long> rangeSum;
   
2.     int countRangeSum(vector<int>& nums, int lower, int upper) {
   
3.         if (nums.size()==0) return 0;
   
4.         size_t n = nums.size();
   
5.         rangeSum.resize(n, 0);
   
6.         long sum = 0;
   
7.         for (int i = 0; i < n; i++) {
   
8.             sum += nums[i];
   
9.             rangeSum[i] = sum;
   
10.         }
    
11.         int result = searchRange(0, n-1, lower, upper);
    
12.         return result;
    
13.     }
    
14.    
    
15.     long getSum(int i, int j) {
    
16.         return rangeSum[j]-rangeSum[i];
    
17.     }
    
18.    
    
19.     int searchRange(int left, int right, int lower, int upper) {
    
20.         if (left == right) return (rangeSum[left]>=lower&&rangeSum[left]<=upper);
    
21.         int mid = (left+right)/2;
    
22.         int count = searchRange(left, mid, lower, upper) + searchRange(mid+1, right, lower, upper);
    
23.         int k = mid+1, j = mid+1;
    
24.         for (int i = left; i <= mid; i++) {
    
25.             while(j<=right && getSum(i,j)<lower) j++;
    
26.             while(k<=right && getSum(i,k)<=upper) k++;
    
27.             count += k-j;
    
28.         }
    
29.         inplace_merge(rangeSum.begin()+left, rangeSum.begin()+mid+1, rangeSum.begin()+right+1);
    
30.         return count;
    
31.     }

复制代码