@[TOC]力扣-1508 子陣列和排序后的區間和
題目描述
給你一個陣列 nums ，它包含 n 個正整數，你需要計算所有非空連續子陣列的和，并將它們按升序排序，得到一個新的包含 n * (n + 1) / 2 個數字的陣列，
請你回傳在新陣列中下標為 left 到 right （下標從 1 開始）的所有數字和（包括左右端點），由于答案可能很大，請你將它對 10^9 + 7 取模后回傳，
示例
輸入：nums = [1,2,3,4], n = 4, left = 1, right = 5
輸出：13
解釋：所有的子陣列和為 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 ，將它們升序排序后，我們得到新的陣列 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] ，下標從 le = 1 到 ri = 5 的和為 1 + 2 + 3 + 3 + 4 = 13 ，
這里我解釋一下，為什么所有的子陣列和為什么是1, 3, 6, 10, 2, 5, 9, 3, 7, 4，
題目說明了，需要計算的是非空連續子陣列的和，因此
前四個，1,3,6，10為陣列{1},{1,2},{1,2,3},{1,2,3,4}
接著三個，2,5,9為陣列{2},{2,3},{2,3,4}
接著后面兩個,3,7為陣列{3},{3,4}
最后一個就是它本身{4}
源代碼
class Solution {
public:
int rangeSum(vector<int>& nums, int n, int left, int right) {
if(nums.empty()) return 0; //如果傳遞的容器陣列為空，則直接回傳0
const int MODULO = 1000000007;
vector<int> num; //定義一個新的容器
int count=0;
for(int i=0;i<n;i++) //上面的文字解釋
{
count=0;
for(int k=i;k<n;k++)
{
count+=nums[k];
num.push_back(count);
}
}
sort(num.begin(),num.end()); //將num按升序排序
int sum=0;
for(int i=left-1;i<right;i++) sum=(sum+num[i])%MODULO;
//注意這里一定是sum=(sum+num[i])%MODULO，不能寫成sum+=num[i]%MODULO，會造成溢位的情況
return sum;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237726.html
標籤：其他
上一篇：用Arduino實作跨年倒計時