首页 > 代码库 > [LintCode] Subarray Sum II
[LintCode] Subarray Sum II
Given an integer array, find a subarray where the sum of numbers is in a given interval. Your code should return the number of possible answers. (The element in the array should be positive)
Given [1,2,3,4]
and interval = [1,3]
, return 4
.
Brainstorming:
This problem asks for all possible answers, which can be O(n^2) in the worst case(all subarrays‘ sum are inside the given interval). Dynamic programming is not useful most of the time
when a problem asks for all possible answers. Because the worst case has O(n^2) answers, so the BCR can not be better than O(n^2) as we need to iterate all subarrays to get the
correct answer.
So the optimal solution is O(n^2) runtime, which usually comes at the format of a nested for loop.
Solution 1. O(n^3) runtime, O(1) space
A straightforward solution is to enumerate all possible subarrays in O(n^2) time, then for each subarray, get its sum and check if this sum is in the given interval.
The implementation of this solution is shown as follows.
1 public class Solution { 2 /** 3 * @param A an integer array 4 * @param start an integer 5 * @param end an integer 6 * @return the number of possible answer 7 */ 8 public int subarraySumII(int[] A, int start, int end) { 9 if(A == null || A.length == 0 || end < start){ 10 return 0; 11 } 12 int cnt = 0; 13 for(int j = 0; j < A.length; j++){ 14 for(int i = 0; i <= j; i++){ 15 int sum = subSum(A, i, j); 16 if(sum >= start && sum <= end){ 17 cnt++; 18 } 19 } 20 } 21 return cnt; 22 } 23 private int subSum(int[] A, int left, int right){ 24 int r = 0; 25 for(int i = left; i <= right; i++){ 26 r += A[i]; 27 } 28 return r; 29 } 30 }
Solution 2. O(n^2) runtime, O(n) space with prefix sum.
Solution 1‘s runtime is O(n^3), not the optimal O(n^2). Applying the BUD(Bottlenecks, Unnecessary work,
Duplicated work) principle, we know that we are doing duplicated work when getting a subarray‘s sum.
Why?
Each time we fix the start and end indices of a subarray, it is only one element different from the previously checked subarray. But this solution does not use this
condition. Instead, it calculates a subarray‘s sum from stratch. What can be optimized here is that we use prefix sum and calculate the sum of the first ith elements
for i = 0, 1, ...... n; This preprocessing step takes O(n) time and O(n) space. When calculating a subarray‘s sum, only a O(1) subtraction is needed , thus making
its runtime to the optimal O(n^2).
This is similiar with the relation between straightforward recursion and dynamic programming. Sacrifice some space for a faster runtime.
1 public class Solution { 2 public int subarraySumII(int[] A, int start, int end) { 3 if(A == null || A.length == 0 || end < start){ 4 return 0; 5 } 6 int[] prefixSum = new int[A.length + 1]; 7 prefixSum[0] = 0; 8 for(int i = 1; i <= A.length; i++){ 9 prefixSum[i] = prefixSum[i - 1] + A[i - 1]; 10 } 11 int cnt = 0; 12 for(int i = 0; i < A.length; i++){ 13 for(int j = i + 1; j <= A.length; j++){ 14 int diff = prefixSum[j] - prefixSum[i]; 15 if(diff >= start && diff <= end){ 16 cnt++; 17 } 18 } 19 } 20 return cnt; 21 } 22 }
Solution 3. O(n^2) runtime, O(1) space
We can further optimize the memory usage from O(n) to O(1). A single integer totalSum is used to keep the current
sum of A[0.....j]. Another integer variable sum is used to keep the current sum of A[i.......j].
1 public class Solution { 2 public int subarraySumII(int[] A, int start, int end) { 3 if(A == null || A.length == 0 || end < start){ 4 return 0; 5 } 6 int totalSum = 0; 7 for(int i = 0; i < A.length; i++){ 8 totalSum += A[i]; 9 } 10 int cnt = 0; 11 for(int j = A.length - 1; j >= 0; j--){ 12 int sum = totalSum; 13 for(int i = 0; i <= j; i++){ 14 if(i > 0){ 15 sum -= A[i - 1]; 16 } 17 if(sum >= start && sum <= end){ 18 cnt++; 19 } 20 } 21 totalSum -= A[j]; 22 } 23 return cnt; 24 } 25 }
Related Problems
Subarray Sum
Subarray Sum Closest
[LintCode] Subarray Sum II