leetcode 327. Count of Range Sum 字段和问题 + 动态规划DP解决 + 字段数 + 暴力求解真好

系统管理员 2022-06-07 01:10 120阅读 0赞

Given an integer array nums, return the number of range sums that lie in \[lower, upper\] inclusive.  
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:  
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:  
Given nums = \[-2, 5, -1\], lower = -2, upper = 2,  
Return 3.  
The three ranges are : \[0, 0\], \[2, 2\], \[0, 2\] and their respective sums are: -2, -1, 2.

我没有想到更好的方法，直接循环做的。

建议和[leetcode 307. Range Sum Query - Mutable 树状数组的一个应用][leetcode 307. Range Sum Query - Mutable] 一起学习

代码如下：

/*
     * 有使用归并排序或者线段树的该方法，可以优化到 O(long(n))
     * 不过我肯定是想不到
     * 所以我这里的是循环遍历的 O(n^2)解法
     * */
    class Solution 
    {
        
        public int countRangeSum(int[] nums, int lower, int upper) 
        {
            if(nums==null || nums.length<=0)
                return 0;
    
            long[] sum=new long[nums.length];
            sum[0]=nums[0];
            for(int i=1;i<nums.length;i++)
                sum[i]=sum[i-1]+nums[i];
            int count=0;
            for(int i=0;i<nums.length;i++)
            {   
                for(int j=i;j<nums.length;j++)
                {
                    long tmp=i==0?sum[j]:sum[j]-sum[i-1];
                    if(tmp>=lower && tmp<=upper)
                        count++;
                }
            }
            return count;
        }
    }

下面是C++的做法，我就是暴力求解的

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int countRangeSum(vector<int>& a, int lower, int upper)
        {
            if (a.size() <= 0)
                return 0;
            vector<long long> sum(a.size(), 0);
            sum[0] = a[0];
            for (int i = 1; i < a.size(); i++)
                sum[i] = sum[i - 1] + a[i];
    
            int count = 0;
            for (int i = 0; i < a.size(); i++)
            {
                for (int j = i; j < a.size(); j++)
                {
                    long long tmp = i == 0 ? sum[j] : sum[j] - sum[i - 1];
                    if (tmp >= lower && tmp <= upper)
                        count++;
                }
            }
            return count;
        }
    };

[leetcode 307. Range Sum Query - Mutable]: http://blog.csdn.net/jackzhang_123/article/details/78133968