In this Leetcode Count of Range Sum problem solution You are given an integer array nums and two integers lower and upper, 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 inclusive, where i <= j.

Leetcode Count of Range Sum problem solution


Problem solution in Python.

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        res = 0
        presum = 0
        sorted_presum = [0]
        for k in range(len(nums)):
            presum += nums[k]
            idx_c = bisect_right(sorted_presum, presum)
            idx_l = bisect_left(sorted_presum, presum - upper)
            idx_r = bisect_right(sorted_presum, presum - lower)
            res += idx_r - idx_l

            sorted_presum[idx_c:idx_c] = [presum]
            
        return res



Problem solution in Java.

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        
        return countRanges(nums, lower, upper);
    }
    
    private int countRanges(int[] nums, int lower, int upper) {
        long sum = 0;
        Map<Long, Integer> sumMap = new HashMap<>();
        int count = 0;
        sumMap.put(0l, 1);
        for(int i=0; i<nums.length; i++) {
            sum = sum + nums[i];
            
            for(int j=lower; j<=upper; j++) {
                Integer prev = sumMap.get(sum-j);
                if(prev != null) {
                    count = count + prev;
                }
            }
            
            if(!sumMap.containsKey(sum)) {
                sumMap.put(sum, 0);
            }
            sumMap.put(sum, sumMap.get(sum) + 1);
        }
        
        return count;
    }
}


Problem solution in C++.

int countRangeSum(vector<int>& A, int lower, int upper) {
        int n = A.size();
        vector<long> prefix(n + 1), aux(n + 1);
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + A[i];
        return countRangeSum(prefix, 0, n + 1, lower, upper, aux);
}

int countRangeSum(vector<long> &prefix, int beg, int end, int lower, int upper, vector<long> &aux) {
    if (end - beg <= 1) return 0;
    auto mid = beg + (end - beg) / 2;
    auto count = countRangeSum(prefix, beg, mid, lower, upper, aux) 
               + countRangeSum(prefix, mid, end, lower, upper, aux);
    auto p = beg;
    for (int i = beg, j = mid, k = mid, t = mid; i < mid; ++i) {
        while (j < end && prefix[j] - prefix[i] <  lower) ++j;
        while (k < end && prefix[k] - prefix[i] <= upper) ++k;
        while (t < end && prefix[t] < prefix[i]) aux[p++] = prefix[t++];
        aux[p++] = prefix[i];
        count += k - j;
    }
    while (beg < p) prefix[beg] = aux[beg++];
    return count;
}


Problem solution in C.

int countConsistentStrings(char * allowed, char ** words, int wordsSize){
int freq[26] = {0};
  int j;
    int count = wordsSize;
    for(int i = 0; i < strlen(allowed); i++){
        freq[allowed[i] - 97]++;
    }

 
    for(int i = 0; i < wordsSize; i++){
        for(j = 0; j < strlen(words[i]); j++){
           if(freq[*(words[i]+ j) -97] == 0){ 
               count = count - 1;
               break;
           }
        } 
    }
    return count;
}