Subarray Sum II

Subarray Sum II

29%

Accepted

Given an integer array, find a subarray where the sum of numbers is between two given interval. Your code should return the number of possible answer.

Have you met this question in a real interview? 

Yes

Example

Given [1,2,3,4] and interval = [1,3], return 4. The possible answers are:

[0, 0]
[0, 1]
[1, 1]
[2, 2]

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
        
        int[] sum = new int[A.length+1];
        sum[0] = 0;
        for(int i = 0; i < A.length; i++){
            sum[i+1] += sum[i] + A[i];
        }
        
        int res = 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(start <= diff && end >= diff){
                    res++;
                }
            }
        }
        return res;
        
    }
}