Untitled
unknown
plain_text
2 years ago
3.2 kB
3
Indexable
import java.util.AbstractMap; class Solution { int largestSubArraySumPossible = 0, smallestSubArraySumPossible = 0; // Returns count of subarrays that have // sum <= target and their total sum. public Map.Entry<Integer, Long> subArraysWithSumLessThanOrEqualTo(int[] nums, int target){ int countOfSuchSubArrays = 0; Long totalSum = 0L; int windowSum = 0; /* currSum intially stores sum of all UNIQUE subArrays in CURRENT WINDOW Note that we dont consider previous ITERATION unique subarrays in current iteration. windowSum stores sum of current window only. Total sum stores sum of all currSums from all iterations. Once we pass given target, we shrink both currSum and windowSum Ex: Iteration 1: Elements {1} -> unique subArrays -> {1} -> currSum = 1, windowSum = sum(elements(left, right)) = sum(1) = 1 Iteration 2: Elements {1, 2} -> unique subArrays -> {1, 2}, {2} -> currSum = (1+2)+2 = 5, windowSum = sum(elements(left, right)) = sum(1+2) = 3 Itr 3: Elements {1, 2, 3} -> unique subArrays -> {3}, {2, 3}, {1, 2, 3} -> currSum = (3 + (2+3) + (1+2+3)) = 14 */ int currSum = 0; int n = nums.length; for (int left = 0, right = 0; right < n; ++right) { currSum += nums[right] * (right - left + 1); windowSum += nums[right]; while (windowSum > target) { currSum -= windowSum; windowSum -= nums[left++]; } countOfSuchSubArrays += right - left + 1; totalSum += currSum; } return new AbstractMap.SimpleEntry<>(Integer.valueOf(countOfSuchSubArrays), Long.valueOf(totalSum)); } public Long firstKSubarraysSum(int[] nums, int k){ int start = smallestSubArraySumPossible, end = largestSubArraySumPossible; while(start < end){ int mid = start + (end-start)/2; if(subArraysWithSumLessThanOrEqualTo(nums, mid).getKey().intValue() < k){ start = mid + 1; } else{ end = mid; } } Map.Entry<Integer, Long> map = subArraysWithSumLessThanOrEqualTo(nums, start); // When count != k, it means there are subarray(s) whose sum is equal to start Long totalOfFirstKSubarraysSum = map.getValue(); int countOfSuchSubArrs = map.getKey().intValue(); return totalOfFirstKSubarraysSum - start * (countOfSuchSubArrs - k); } public int rangeSum(int[] nums, int n, int left, int right) { int mod = (int) 1e9 + 7; int ans = 0; smallestSubArraySumPossible = nums[0]; for(int i=0; i<n; i++){ largestSubArraySumPossible+=nums[i]; smallestSubArraySumPossible = Math.min(smallestSubArraySumPossible, nums[i]); } ans = (int)((firstKSubarraysSum(nums, right) % mod) - (firstKSubarraysSum(nums, left-1) % mod)); return ans%mod; } }
Editor is loading...