leetcode 1508. Range Sum of Sorted Subarray Sums 子数组和排序后的区间和

Problem: 1508. Range Sum of Sorted Subarray Sums 子数组和排序后的区间和

计算出前缀和，然后得到所有子数组的累加和，排序，然后计算区间内的累加和

Code

class Solution { public: const int mod = 1e9 + 30 - 23; int rangeSum(vector<int>& nums, int n, int left, int right) { vector<int> prefix{0}; for(int i = 0; i < n; i++) prefix.push_back(prefix.back() + nums[i]); vector<int> ret; for(int i = 0; i < n; i++) { for(int j = i+1; j <= n; j++) { ret.push_back(prefix[j] - prefix[i]); } } sort(ret.begin(), ret.end()); long long s = 0; for(int i = left; i <= right; i++) s = (ret[i - 1] + s) ; return s% mod; } };