leetcode 327. Count of Range Sum

ゞ浴缸里的玫瑰 2022-08-20 02:18 156阅读 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.

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