Description

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. 同subarray sum相同的思路，sum[i][j] = sum[0][j] - sum[0][i]，先求得sum array，再逐一比对sum[i][j]是否在interval范围之内即可
2. 两个指针i, j 之间的子序列sum小于interval或在interval之间时j++，大于interval时i++，j再从i开始重新来记

int count = 0;
for (int i = 0; i < length; i++) {
    int j = i; 
    int sum = arr[j];
    while (sum <= interval[1]) {
        if (sum >= interval[0]) {
            count++;
        }
        j++;
        sum += arr[j];
    }
}