LeetCode 327 Count of Range Sum

题目链接:Count of Range Sum

思路来自:http://algobox.org/count-of-range-sum/

题意:给一个数组nums,给出最大值upper,最小值lower,求有多少个区间 \([i,j](i\leqslant j)\) 满足 \(lower \leqslant \sum_{k=i}^{j}nums_k\leqslant upper\)

 

因为有负数,前缀和没有了单调性,就不能用二指针的方法。

一开始想到应该是分治,但是合并的方法没有想对。

想的是先预处理前缀和,再记录每个和的个数,然后枚举左区间的坐标,算出右区间的临界值。

但是记录和的个数就要用map,算临界值需要二分查找,时间复杂度应该是 \(O(nlog(n)log(n))\)

感觉想复杂了,于是百度了一发,发现了一个巧妙的解法。

 

先预处理前缀和 \(sum_{i+1}=sum_i+nums_i\) ,于是区间[i,j]的和等于 \(sum_j-sum_i\) (这里和平时的写法不一样,是方便后面处理归并时的坐标)

巧妙的地方在于,利用归并排序,使左右区间的sum有序,而且不会破坏左区间和右区间的相对位置,这样就可以用二指针了。

枚举左区间的坐标i,找到右区间中:

第一个 \(sum_{rl}-sum_i\) 大于等于lower的临界值坐标rl

第一个 \(sum_{rr}-sum_i\) 大于upper的临界值坐标rr

则贡献的区间个数为 \(rr-rl\)

因为左右区间都是单调递增的,当i向右移,rl和rr也只可能向右移,所以合并时复杂度为 \(O(n)\)

计算完后进行归并排序,保证当前区间sum有序

因为只需要计算区间的个数,所以利用前缀和就可以避开不能改变位置的问题,巧妙的利用排序求解。

所以不能因为是统计区间就习惯性的排除排序这种方法啊=。=

还要注意要用long,数据的范围是int,但两个数相加就可能超出int范围

时间复杂度 \(O(nlog(n))\)

 

Categories: LeetCode