给定一个整数数组 nums,返回区间和在 [lower, upper] 之间的个数,包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中,位置从 i 到 j 的元素之和,包含 i 和 j (i ≤ j)。
说明:
最直观的算法复杂度是 O(n2) ,请在此基础上优化你的算法。
示例:
输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3
解释: 3个区间分别是: [0,0], [2,2], [0,2],它们表示的和分别为: -2, -1, 2。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-of-range-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
1 class Solution { 2 public: 3 //最暴力的解法 4 int countRangeSum(vector<int>& nums, int lower, int upper) { 5 int res=0; 6 for(int i=1;i<=nums.size();i++) 7 { 8 for(int j=0;j<nums.size()-i+1;j++) 9 { 10 long long sum=0; 11 for(int k=j;k<j+i;k++) 12 sum+=(long long)nums[k]; 13 if(sum>=lower&&sum<=upper)res++; 14 } 15 } 16 return res; 17 } 18 };
class Solution { public: //增加一个数组 存储长度为len起始位置为i的加和 每次都存储在长度为len的子集的最后一位 int countRangeSum(vector<int>& nums, int lower, int upper) { int res=0; vector<long> sum_vec; for(auto item:nums) { if(item>=lower&&item<=upper)res++; sum_vec.push_back(item); } for(int i=1;i<nums.size();i++) { for(int j=nums.size()-1;j>=i;j--) { sum_vec[j]=sum_vec[j-1]+(long)nums[j]; if(sum_vec[j]>=lower&&sum_vec[j]<=upper)res++; } } return res; } };
1 class Solution { 2 public: 3 //存储前缀和 通过60/61个 4 int countRangeSum(vector<int>& nums, int lower, int upper) { 5 int res=0; 6 vector<long> prefix_sum(nums.size()+1,0); 7 for(int i=1;i<=nums.size();i++) 8 prefix_sum[i]=prefix_sum[i-1]+(long)nums[i-1]; 9 for(int k=1;k<=nums.size();k++) 10 { 11 for(int i=k;i<=nums.size();i++) 12 { 13 long val=prefix_sum[i]-prefix_sum[i-k]; 14 if(val>=lower&&val<=upper)res++; 15 } 16 } 17 return res; 18 } 19 };