const auto right = upper_bound(sum_from_start.cbegin(), sum_from_start.cbegin() + j + 1, sum_from_start[j + 1] - start); result += (right - sum_from_start.cbegin()) - (left - sum_from_start.cbegin()); } return result; } }; // Time: O(n^2) // Space: O(n) class Solution2 { public: /** * @param A an integer array * @param start an integer * @param end an integer * @return the number of possible answer */ int subarraySumII(vector& A, int start, int end) { // sum_from_start[i] denotes sum for 0 ~ i - 1. vector sum_from_start(A.size() + 1); partial_sum(A.cbegin(), A.cend(), sum_from_start.begin() + 1); int result = 0; for (int i = 0, j = 0; j < A.size(); ++j) { int k = i; while (k <= j) { if (sum_from_start[j + 1] - sum_from_start[k] >= start && sum_from_start[j + 1] - sum_from_start[k] <= end) { ++result; } ++k; } } return result; } }; 4:["$","div",null,{"children":[["$","header",null,{"children":[["$","div",null,{"className":"text-3xl text-bold p-0 mt-2 mb-2","children":["$","h1",null,{"children":["Subarray Sum II",["$","span",null,{"className":"font-mono text-sm text-gray-500","children":"(LintCode 404):"}]]}]}],""]}],["$","article",null,{"children":[["$","div",null,{"className":"p-0","dangerouslySetInnerHTML":{"__html":"

Problem description: Visit and Support LintCode Search via
Diff

Problem