题目地址： https://leetcode.com/PRoblems/count-of-range-sum/?tab=Description 题目描述 ：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.
我的代码 ：
class Solution {public: int mergeRangeSum(vector<long>& sums,int lower,int upper,int start,int end){ if(end-start<=1) return 0; int average,n,m; n=m=average=(start+end)/2; int count=mergeRangeSum(sums,lower,upper,start,average)+mergeRangeSum(sums,lower,upper,average,end); for(int i=start;i<average;i++){ while(m < end && sums[m] - sums[i] < lower) m++; while(n < end && sums[n] - sums[i] <= upper) n++; count+=(n-m); } inplace_merge(sums.begin()+start,sums.begin()+average,sums.begin()+end); return count; } int countRangeSum(vector<int>& nums, int lower, int upper) { int n=nums.size(); vector<long> sums; sums.push_back(0); for(int i=0;i<n;i++) sums.push_back(sums[i]+nums[i]); return mergeRangeSum(sums,lower,upper,0,n+1); }};解题思路 ： 用sum[i]表示原数组的前i个数之和，且令sum[0]=0;如此将数组的区间之和转换为sum中两项之差。 然后，对sum进行分析，采用分治的思想，将sum分为前后均匀的两部分，sum中的任意两项，或者都属于前一部分，或者都属于后一部分，或者一个属于前一部分，一个属于后一部分。对于前两种情况，如同数组长度减短，可递归求解。 而对于最后一种情况，由于一个属于前一部分，一个属于后一部分，因此必定是属于后一部分的元素减去属于前一部分的元素，可将前一部分与后一部分分别排序而不会影响结果。 至此，只需对前一部分的每个元素，找出后一部分的两个临界点，由于后一部分已经是有序的，可直接采用二分法求解。复杂度为O(nlogn)。 然而，若采用二分法，则未曾有效利用前一部分的有序性。由前一部分的有序性，我们可知对于前一部分的两个元素i，j，假设其对应后半部分上界为m，n；可知当j>i时，必有m>=n;如此，可直接遍历，复杂度为O(n)，但由于排序复杂度为O(nlogn)，所以总复杂依然为O(nlogn)。但相较于二分法更好。
新闻热点
疑难解答
