1508. 子数组和排序后的区间和

1508. 子数组和排序后的区间和

暴力

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        vector<int> newnums;
        const int mod=1e9+7;
        for(int i=0;i<n;i++){
            int cursum=0;
            for(int j=i;j<n;j++){
                cursum+=nums[j];
                newnums.push_back(cursum);
            }
        }
        
        sort(newnums.begin(),newnums.end());
        
        int res=0;
        for(int i=left-1;i<=right-1;i++){
            res+=newnums[i];
            res%=mod;
        }
        return res;
    }
};

前缀和+二分

不会。。