Subarray Sum II 404
Question
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)
Example
Given [1,2,3,4] and interval = [1,3], return 4. The possible answers are:
[0, 0] [0, 1] [1, 1] [2, 2]
Solution
方法1: 和I一样,用prefix来解。首先计算prefix,然后根据prefix来计算每一段subarray的sum。右边prefix-左边prefix等于中间这一段subarray的sum。左边prefix从0枚举到n-1,右边prefix从当前左边往右一位开始枚举到n,这样可以得到所有sunarray的sum,每一个sum如果在interval之内则count增加1个。O(n^2)。
方法2: 和1思想其实一样,每次右边界j向右移动一位,然后枚举左边界从0到j-1,计算左右边界array的sum,看这些sum是否在interval中。
代码如下:
public class Solution {
/**
* @param A an integer array
* @param start an integer
* @param end an integer
* @return the number of possible answer
*/
public int subarraySumII(int[] A, int start, int end) {
// Write your code here
if(A == null || A.length == 0 || start > end){
return 0;
}
//preix version
int[] sum = new int[A.length + 1];
sum[0] = 0;
for(int i = 1; i <= A.length; i++){
sum[i] = sum[i - 1] + A[i - 1];
}
int count = 0;
for(int i = 0; i < A.length; i++){
for(int j = i + 1; j <= A.length; j++){
int diff = sum[j] - sum[i];
if(diff >= start && diff <= end){
count++;
}
}
}
return count;
//My version
// int j = 0;
// int count = 0;
// int sum = 0;
// while(j < A.length){
// sum += A[j];
// if(sum >= start && sum <= end){
// count++;
// }
// int i = 0;
// int temp = sum - A[i];
// while(i < j){
// if(temp >= start && temp <= end){
// count++;
// }
// i++;
// temp -= A[i];
// }
// j++;
// }
// return count;
}
}