推 sustainer123: 大師 08/04 10:14
→ Smallsh: 大師 08/04 10:16
推 sustainer123: 我還以為這題考backtracking 我就這樣了 08/04 10:16
1508 range sum of sorted subarray sums
題目:
給你一個vector nums，其中包含n個整數，求當你計算出nums所有subarray的個別和
後，將其排序由小到大後，從1-index系統中，從題目給的數字right開始一路加到
left後的這些subarray sum的總和
思路:
可以很直觀的照題目敘述先利用一個vector存放nums所有的subarray sum，然後sort
再根據題目給的right left求這段的和。
但題目下面的topic可以看到是有binary search 還有2 pointer的，editorial裡面
有介紹另一個用到binary search的最佳解。
int rangeSum(vector<int>& nums, int n, int left, int right) {
vector<long long > pre_ans;
for(int i=0;i<n;++i){
long long temp=0;
for(int j=i;j<n;++j){
temp+=nums[j];
pre_ans.push_back(temp);
}
}
sort(pre_ans.begin(),pre_ans.end());
int mod = 1e9 + 7;
long long ans=0;
for(int i=left-1;i<right;++i){
ans+=pre_ans[i];
}
return ans%mod;
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.16.83 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722737533.A.705.html