Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/04 10:12)推噓2(2推 0噓 1→)留言3則, 2人參與討論串631/1553 (看更多)
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
推
08/04 10:14,
1年前
, 1F
08/04 10:14, 1F
→
08/04 10:16,
1年前
, 2F
08/04 10:16, 2F
推
08/04 10:16,
1年前
, 3F
08/04 10:16, 3F
討論串 (同標題文章)
完整討論串 (本文為第 631 之 1553 篇)：