Medium
Related Topics: Array / Two Pointers / Binary Search / Sorting
LeetCode Source

解題想法

1. 用 arr 存所有 subarray 的加總
2. 排序 arr 由小至大
3. 用 res 加總 arr 的值，index 從 left-1 到 right-1 (因為 index 從 1 開始)
4. 題目要求最後的值要用 1e9+7 取餘數

Complexity

Time Complexity: O(n^2logn)
Space Complexity: O(n^2)

Python

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        arr = []

        for i in range(len(nums)):
            temp = 0
            for j in range(i, len(nums)):
                temp += nums[j]
                arr.append(temp)

        arr.sort()

        res = 0

        for i in range(left-1, right):
            res += arr[i]

        return res % (10**9 + 7)

C++

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        int MOD = 1e9 + 7;
        vector<int> arr;

        for (int i = 0; i < nums.size(); i++) {
            int temp = 0;
            for (int j = i; j < nums.size(); j++) {
                temp += nums[j];
                arr.push_back(temp);
            }
        }

        sort(arr.begin(), arr.end());

        int res = 0;

        for (int i = left-1; i <= right-1; i++) {
            res += arr[i];
            res %= MOD;
        }
        return res;
    }
};