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.
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; }
0 Comments