10

力扣-1508 子数组和排序后的区间和

 3 years ago
source link: https://blog.csdn.net/weixin_45774972/article/details/111400375
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

力扣-1508 子数组和排序后的区间和

hero_th 2020-12-19 09:47:38 162

@[TOC]力扣-1508 子数组和排序后的区间和

给你一个数组 nums ,它包含 n 个正整数。你需要计算所有非空连续子数组的和,并将它们按升序排序,得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为 left 到 right (下标从 1 开始)的所有数字和(包括左右端点)。由于答案可能很大,请你将它对 10^9 + 7 取模后返回。

输入:nums = [1,2,3,4], n = 4, left = 1, right = 5
输出:13
解释:所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后,我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。

这里我解释一下,为什么所有的子数组和为什么是1, 3, 6, 10, 2, 5, 9, 3, 7, 4,
题目说明了。需要计算的是非空连续子数组的和,因此
前四个,1,3,6,10为数组{1},{1,2},{1,2,3},{1,2,3,4}
接着三个,2,5,9为数组{2},{2,3},{2,3,4}
接着后面两个,3,7为数组{3},{3,4}
最后一个就是它本身{4}
class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        if(nums.empty()) return 0;   //如果传递的容器数组为空,则直接返回0
        const int MODULO = 1000000007;
        vector<int> num;   //定义一个新的容器
        int count=0;
        for(int i=0;i<n;i++) //上面的文字解释
        {
            count=0;
            for(int k=i;k<n;k++)
            {
                count+=nums[k];
                num.push_back(count);
            }
        }
        sort(num.begin(),num.end());   //将num按升序排序
        int sum=0;
        for(int i=left-1;i<right;i++) sum=(sum+num[i])%MODULO;
        //注意这里一定是sum=(sum+num[i])%MODULO,不能写成sum+=num[i]%MODULO,会造成溢出的情况
        return sum;
    }
};


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK