Precompute cumulative sums in O(n) so any range sum query [l..r] answers in O(1). prefix[i] = sum of nums[0..i-1], then rangeSum = prefix[r+1] − prefix[l].
One pass builds the prefix array of size n+1. Each subsequent range query is a single subtraction. Space is O(n) for the prefix array, O(1) extra per query.
// ── 1. Build prefix sum array ───────────────────────────────────── int[] prefix = new int[nums.length + 1]; // prefix[0] = 0 (sentinel) for (int i = 0; i < nums.length; i++) { prefix[i + 1] = prefix[i] + nums[i]; // running sum } // ── 2. Range sum query: O(1) per query ─────────────────────────── // sum of nums[l..r] = prefix[r+1] - prefix[l] int rangeSum = prefix[r + 1] - prefix[l]; // ── 3. Count subarrays with sum = k (HashMap variant) ──────────── Map<Integer, Integer> cnt = new HashMap<>(); cnt.put(0, 1); // empty prefix — handle subarrays starting at index 0 int sum = 0, count = 0; for (int num : nums) { sum += num; count += cnt.getOrDefault(sum - k, 0); // if (sum-k) seen → subarrays sum to k cnt.merge(sum, 1, Integer::sum); } return count;