Paste_Image.png

package subArrays;

import static org.junit.Assert.assertEquals;

public class ProductSubarray {
    
    /*
     * We define a subarray of an array, numbers, 
     * to be a contiguous block of numbers' elements having a length 
     * that is less than or equal to the length of the numbers array. 
     * For example, the subarrays of numbers = [1, 2, 3] are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3]. 
     * If we were to then find the products for each respective subarray, they would be 1, 2, 3, 1 × 2 = 2, 2 × 3 = 6, and 1 × 2 × 3 = 6.
     * 找到所有连续子数组的乘积和 < k 的子数组， 并返回他们的个数
     */
    public static int SubarrayProducts(int[] numbers, int k) {
        if (numbers == null) {
            return -1;
        }
        
        int n = numbers.length;
        int count = 0;
        for (int left = 0; left < n; left++) {
            int product = 1;
            for (int right = left; right < n; right++) {
                //first number 
                if (product * numbers[right] < k) {
                    product *= numbers[right];
                    count++;
                } else {
                    break;
                }
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        
        assertEquals(SubarrayProducts(ArraySerializer.deserialize("[1,2,3]"), 7), 6);
        System.out.println(SubarrayProducts(ArraySerializer.deserialize("[1,2,3]"), 7)); // 6
        
        assertEquals(SubarrayProducts(ArraySerializer.deserialize("[1,2,3,5]"), 7), 7);
        System.out.println(SubarrayProducts(ArraySerializer.deserialize("[1,2,3,5]"), 7)); // 7
        
        assertEquals(SubarrayProducts(ArraySerializer.deserialize("[2,4,3,2]"), 7), 5);
        System.out.println(SubarrayProducts(ArraySerializer.deserialize("[2,4,3,2]"), 7)); // 5
    }
}