leetcode 327. Count of Range Sum-蒲公英云

leetcode 327. Count of Range Sum

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.

#include "stdafx.h"
#include<iostream>
//#include<vector>
//#include<algorithm>
using namespace std;
/*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.*/
struct Check{
    int lower;
    int upper;
public:
    Check(int l, int u){
        lower = l;
        upper = u;
    }
    Check(){}
    bool in_range(int value)
    {
        return (value <= upper) && (value >= lower);
    }
};
int count_num(int*begin,int*end,int lower, int upper)
{
    int num = 0;
    while (end != begin)
    {
        if (*begin >= lower&&*begin <= upper)
            num++;
        begin++;
    }
    return num;
}
int countRangeSum(int* nums, int numsSize, int lower, int upper)
{
    int*sumarray = new int[numsSize];
    memset(sumarray, 0, sizeof(int)*numsSize);
    sumarray[0] = nums[0];
    for (int i = 1; i < numsSize; i++)
    {
        sumarray[i] = sumarray[i - 1] + nums[i];
    }
    /*int countnum = count_if(sumarray, sumarray + numsSize, Check(lower, upper).in_range);
    for (int i = 1; i < numsSize; i++)
    {
        Check check(lower + sumarray[i - 1], upper + sumarray[i - 1]);
        countnum += count_if(sumarray + i, sumarray + numsSize, check.in_range);
    }*/
    int countnum = count_num(sumarray , sumarray + numsSize, lower, upper);;
    for (int i = 1; i < numsSize; i++)
    {
        countnum += count_num(sumarray + i, sumarray + numsSize, lower + sumarray[i - 1], upper + sumarray[i - 1]);
    }
    delete[]sumarray;
    return countnum;
}
int _tmain(int argc, _TCHAR* argv[])
{
    int nums[3] = { -2, 5, -1 };
    cout << countRangeSum(nums, 3, -2, 2);
    system("pause");
    return 0;
}