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;
}