算法（如何计算乘积和总和相等的子数组的个数（）） _数据结构

本文概述

C ++
Java
Python3
C#
的PHP

给定n个数字的数组。我们需要计算具有乘积和元素总和相等的子数组的数量
例子：

Input: arr[] = {1, 3, 2} Output : 4 The subarrays are : [0, 0] sum = 1, product = 1, [1, 1] sum = 3, product = 3, [2, 2] sum = 2, product = 2 and [0, 2] sum = 1+3+2=6, product = 1*3*2 = 6Input : arr[] = {4, 1, 2, 1} Output : 5

这个想法很简单, 我们检查每个子数组是否乘积和其元素的总和是否相等。如果是, 则将计数器变量加1
C ++

// C++ program to count subarrays with // same sum and product. #include< bits/stdc++.h> using namespace std; // returns required number of subarrays int numOfsubarrays( int arr[] , int n) { int count = 0; // Initialize result// checking each subarray for ( int i=0; i< n; i++) { int product = arr[i]; int sum = arr[i]; for ( int j=i+1; j< n; j++) { // checking if product is equal // to sum or not if (product==sum) count++; product *= arr[j]; sum += arr[j]; }if (product==sum) count++; } return count; }// driver function int main() { int arr[] = {1, 3, 2}; int n = sizeof (arr)/ sizeof (arr[0]); cout < < numOfsubarrays(arr , n); return 0; }

Java

// Java program to count subarrays with // same sum and product.class GFG { // returns required number of subarrays static int numOfsubarrays( int arr[] , int n) { int count = 0 ; // Initialize result// checking each subarray for ( int i= 0 ; i< n; i++) { int product = arr[i]; int sum = arr[i]; for ( int j=i+ 1 ; j< n; j++) { // checking if product is equal // to sum or not if (product==sum) count++; product *= arr[j]; sum += arr[j]; }if (product==sum) count++; } return count; }// Driver function public static void main(String args[]) { int arr[] = { 1 , 3 , 2 }; int n = arr.length; System.out.println(numOfsubarrays(arr , n)); } }

Python3

# python program to # count subarrays with # same sum and product.# returns required # number of subarrays def numOfsubarrays(arr, n):count = 0 # Initialize result# checking each subarray for i in range (n):product = arr[i] sum = arr[i] for j in range (i + 1 , n):# checking if product is equal # to sum or not if (product = = sum ): count + = 1product * = arr[j] sum + = arr[j]if (product = = sum ): count + = 1return count# Driver codearr = [ 1 , 3 , 2 ] n = len (arr) print (numOfsubarrays(arr , n))# This code is contributed # by Anant Agarwal.

// C# program to count subarrays // with same sum and product. using System; class GFG {// returns required number // of subarrays static int numOfsubarrays( int []arr , int n) {// Initialize result int count = 0; // checking each subarray for ( int i = 0; i < n; i++) { int product = arr[i]; int sum = arr[i]; for ( int j = i + 1; j < n; j++) {// checking if product is // equal to sum or not if (product == sum) count++; product *= arr[j]; sum += arr[j]; }if (product == sum) count++; } return count; }// Driver Code public static void Main() { int []arr = {1, 3, 2}; int n = arr.Length; Console.Write(numOfsubarrays(arr , n)); } }// This code is contributed by Nitin Mittal.

的PHP

< ?php // PHP program to count subarrays // with same sum and product.// function returns required // number of subarrays function numOfsubarrays( $arr , $n ) { // Initialize result $count = 0; // checking each subarray for ( $i = 0; $i < $n ; $i ++) { $product = $arr [ $i ]; $sum = $arr [ $i ]; for ( $j = $i + 1; $j < $n ; $j ++) {// checking if product is // equal to sum or not if ( $product == $sum ) $count ++; $product *= $arr [ $j ]; $sum += $arr [ $j ]; }if ( $product == $sum ) $count ++; } return $count ; }// Driver Code $arr = array (1, 3, 2); $n = sizeof( $arr ); echo (numOfsubarrays( $arr , $n )); // This code is contributed by Ajit. ?>

输出如下：