定义: 针对数组A[1,n],,前k个数组元素之和就是前缀和的概念。
下面给出样例题:
题目: 327. 区间和的个数
网址: https://leetcode-cn.com/problems/count-of-range-sum/
代码
class Solution { public: int countRangeSum(vector<int>& nums, int lower, int upper) { int n = nums.size(); if(n==0 ||(lower>upper)) return 0; vector<long> data; long sum=0; data.push_back(sum); for(auto& digit: nums){ sum += digit; data.push_back(sum); } return countRangeSort(data, lower, upper, 0, n); } int countRangeSort(vector<long>& data, int lower, int upper, int left, int right){ if(left==right) return 0; else{ int mid = (left + right)/2; int n1 = countRangeSort(data, lower, upper, left, mid); int n2 = countRangeSort(data, lower, upper, mid+1, right); int ret = n1 + n2; //计算当前状态的所有符合的和 int l = mid+1; int r = mid+1; int i = left; while(i<=mid){ //至于为什么能够用归并,其实是利用了前缀数长的序列一定是在右边,所以一定再排序前面先进行统计,否则就出问题。 while(l<=right && data[l] - data[i] < lower) l++; while(r<=right && data[r] - data[i] <= upper ) r++; ret += (r-l); i++; } //排序 vector<long> tmp(right-left+1); //这个地方实现方法多种,可以考虑是移位实现不使用额外空间 i=left; int j = mid+1; int k = 0; while(i<=mid && j<=right){ if(data[i]<=data[j]) tmp[k++] = data[i++]; else tmp[k++] = data[j++]; } while(i<=mid) tmp[k++]=data[i++]; while(j<=right) tmp[k++]=data[j++]; for(i=0;i<=right-left;i++){ data[i+left]=tmp[i]; } return ret; } } };
这个代码是排序-区间和中归并算法的代码,其中的核心一共两个,一个就是前缀和的概念,另一个就是归并排序。