推 JenniferLope: 大師 08/04 14:48
推 oin1104: 大師 08/04 14:48
推 lambogodar: 大師 08/04 14:53
→ smart0eddie: 大師 08/04 15:00
※ 引述《eden6197 (:))》之銘言：
: 題目:
: 問你subarray的和sort之後
: left到right加起來是多少
: 思路:
: 照做
: 把subarray 通通弄出來之後
: sort加起來
思路:
用所有子陣列產生新陣列之後排序
我看他數字範圍是1~100 就算有1000個也沒多大
計數排序很好做
java code
-----------------------------------------
class Solution {
public int rangeSum(int[] nums, int n, int left, int right) {
int[] cnt = new int[100001];
int MOD = 1000000007;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
cnt[sum]++;
}
}
int res = 0;
int i = 0;
int idx = 1;
while (idx <= right) {
if (cnt[i]-- <= 0) {
i++;
continue;
}
if (idx++ >= left) {
res = (res + i) % MOD;
}
}
return res;
}
}
-----------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722754007.A.5B5.html