给定一个数组arr[]，一个整数K和一个和。任务是检查是否存在K个元素的子数组，其和等于给定的和。如果大小为K的任何子阵列的和等于给定的和，则打印是，否则打印否。 例子 :
null
Input: arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20} k = 4, sum = 18Output: YESSubarray = {4, 2, 10, 2}Input: arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20} k = 3, sum = 6Output: YES
A. 简单解决方案 就是使用嵌套循环，我们检查大小为k的每个子数组。 以下是上述方法的实施情况：
C++
// CPP program to check if any Subarray of size // K has a given Sum #include <iostream> using namespace std; // Function to check if any Subarray of size K // has a given Sum bool checkSubarraySum( int arr[], int n, int k, int sum) { // Consider all blocks starting with i. for ( int i = 0; i < n - k + 1; i++) { int current_sum = 0; // Consider each subarray of size k for ( int j = 0; j < k; j++) current_sum = current_sum + arr[i + j]; if (current_sum == sum) return true ; } return false ; } // Driver code int main() { int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int sum = 18; int n = sizeof (arr) / sizeof (arr[0]); if (checkSubarraySum(arr, n, k, sum)) cout << "YES" ; else cout << "NO" ; return 0; } |
JAVA
// Java program to check // if any Subarray of size // K has a given Sum class GFG { // Function to check if any // Subarray of size K has // a given Sum static boolean checkSubarraySum( int arr[], int n, int k, int sum) { // Consider all blocks // starting with i. for ( int i = 0 ; i < n - k + 1 ; i++) { int current_sum = 0 ; // Consider each // subarray of size k for ( int j = 0 ; j < k; j++) current_sum = current_sum + arr[i + j]; if (current_sum == sum) return true ; } return false ; } // Driver code public static void main(String args[]) { int arr[] = new int [] { 1 , 4 , 2 , 10 , 2 , 3 , 1 , 0 , 20 }; int k = 4 ; int sum = 18 ; int n = arr.length; if (checkSubarraySum(arr, n, k, sum)) System.out.println( "YES" ); else System.out.println( "NO" ); } } // This code is contributed // by Kirti_Mangal |
Python3
# Python3 program to check # if any Subarray of size # K has a given Sum # Function to check if # any Subarray of size # K, has a given Sum def checkSubarraySum(arr, n, k, sum ): # Consider all blocks # starting with i. for i in range (n - k + 1 ): current_sum = 0 ; # Consider each subarray # of size k for j in range (k): current_sum = (current_sum + arr[i + j]); if (current_sum = = sum ): return True ; return False ; # Driver code arr = [ 1 , 4 , 2 , 10 , 2 , 3 , 1 , 0 , 20 ]; k = 4 ; sum = 18 ; n = len (arr); if (checkSubarraySum(arr, n, k, sum )): print ( "YES" ); else : print ( "NO" ); # This code is contributed by mits |
C#
// C# program to check if any // Subarray of size K has a given Sum using System; class GFG { // Function to check if any Subarray // of size K has a given Sum static bool checkSubarraySum( int [] arr, int n, int k, int sum) { // Consider all blocks // starting with i. for ( int i = 0; i < n - k + 1; i++) { int current_sum = 0; // Consider each // subarray of size k for ( int j = 0; j < k; j++) current_sum = current_sum + arr[i + j]; if (current_sum == sum) return true ; } return false ; } // Driver code static void Main() { int [] arr = new int [] { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int sum = 18; int n = arr.Length; if (checkSubarraySum(arr, n, k, sum)) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code is contributed // by mits |
PHP
<?php // PHP program to check // if any Subarray of size // K has a given Sum // Function to check if // any Subarray of size // K, has a given Sum function checkSubarraySum( $arr , $n , $k , $sum ) { // Consider all blocks starting with i. for ( $i = 0; $i < $n - $k + 1; $i ++) { $current_sum = 0; // Consider each subarray of size k for ( $j = 0; $j < $k ; $j ++) $current_sum = $current_sum + $arr [ $i + $j ]; if ( $current_sum == $sum ) return true; } return false; } // Driver code $arr = array (1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $sum = 18; $n = sizeof( $arr ); if (checkSubarraySum( $arr , $n , $k , $sum )) echo "YES" ; else echo "NO" ; // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to check if any // Subarray of size K has a given Sum // Function to check if any Subarray // of size K has a given Sum function checkSubarraySum(arr, n, k, sum) { // Consider all blocks // starting with i. for (let i = 0; i < n - k + 1; i++) { let current_sum = 0; // Consider each // subarray of size k for (let j = 0; j < k; j++) current_sum = current_sum + arr[i + j]; if (current_sum == sum) return true ; } return false ; } let arr = [ 1, 4, 2, 10, 2, 3, 1, 0, 20 ]; let k = 4; let sum = 18; let n = arr.length; if (checkSubarraySum(arr, n, k, sum)) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by mukesh07. </script> |
输出：
YES
时间复杂性 ：O（n*k） 一 有效解决方案 就是检查 滑动窗口技术 同时检查总和是否等于给定的总和。
C++
// CPP program to check if any Subarray of size // K has a given Sum #include <iostream> using namespace std; // Function to check if any Subarray of size K // has a given Sum bool checkSubarraySum( int arr[], int n, int k, int sum) { // Check for first window int curr_sum = 0; for ( int i=0; i<k; i++) curr_sum += arr[i]; if (curr_sum == sum) return true ; // Consider remaining blocks ending with j for ( int j = k; j < n; j++) { curr_sum = curr_sum + arr[j] - arr[j-k]; if (curr_sum == sum) return true ; } return false ; } // Driver code int main() { int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int sum = 18; int n = sizeof (arr) / sizeof (arr[0]); if (checkSubarraySum(arr, n, k, sum)) cout << "YES" ; else cout << "NO" ; return 0; } |
JAVA
// Java program to check if any Subarray of size // K has a given Sum class GFG{ // Function to check if any Subarray of size K // has a given Sum static boolean checkSubarraySum( int [] arr, int n, int k, int sum) { // Check for first window int curr_sum = 0 ; for ( int i= 0 ; i<k; i++) curr_sum += arr[i]; if (curr_sum == sum) return true ; // Consider remaining blocks ending with j for ( int j = k; j < n; j++) { curr_sum = curr_sum + arr[j] - arr[j-k]; if (curr_sum == sum) return true ; } return false ; } // Driver code public static void main(String[] args) { int [] arr= new int []{ 1 , 4 , 2 , 10 , 2 , 3 , 1 , 0 , 20 }; int k = 4 ; int sum = 18 ; int n = arr.length; if (checkSubarraySum(arr, n, k, sum)) System.out.println( "YES" ); else System.out.println( "NO" ); } } // This code is contributed by mits |
Python3
# Python3 program to check if any # Subarray of size K has a given Sum # Function to check if any Subarray # of size K has a given Sum def checkSubarraySum(arr, n, k, sumV): # Check for first window curr_sum = 0 for i in range ( 0 , k): curr_sum + = arr[i] if (curr_sum = = sumV): return true # Consider remaining blocks # ending with j for j in range (k, n): curr_sum = (curr_sum + arr[j] - arr[j - k]) if (curr_sum = = sumV) : return True return False # Driver code arr = [ 1 , 4 , 2 , 10 , 2 , 3 , 1 , 0 , 20 ] k = 4 sumV = 18 n = len (arr) if (checkSubarraySum(arr, n, k, sumV)): print ( "YES" ) else : print ( "NO" ) # This code is contributed # by Yatin Gupta |
C#
// C# program to check if any Subarray of size // K has a given Sum using System; class GFG{ // Function to check if any Subarray of size K // has a given Sum static bool checkSubarraySum( int [] arr, int n, int k, int sum) { // Check for first window int curr_sum = 0; for ( int i=0; i<k; i++) curr_sum += arr[i]; if (curr_sum == sum) return true ; // Consider remaining blocks ending with j for ( int j = k; j < n; j++) { curr_sum = curr_sum + arr[j] - arr[j-k]; if (curr_sum == sum) return true ; } return false ; } // Driver code static void Main() { int [] arr= new int []{ 1, 4, 2, 10, 2, 3, 1, 0, 20 }; int k = 4; int sum = 18; int n = arr.Length; if (checkSubarraySum(arr, n, k, sum)) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code is contributed by mits |
PHP
<?php // PHP program to check if any // Subarray of size K has a given Sum // Function to check if any Subarray // of size K has a given Sum function checkSubarraySum( $arr , $n , $k , $sum ) { // Check for first window $curr_sum = 0; for ( $i = 0; $i < $k ; $i ++) $curr_sum += $arr [ $i ]; if ( $curr_sum == $sum ) return true; // Consider remaining blocks // ending with j for ( $j = $k ; $j < $n ; $j ++) { $curr_sum = $curr_sum + $arr [ $j ] - $arr [ $j - $k ]; if ( $curr_sum == $sum ) return true; } return false; } // Driver code $arr = array ( 1, 4, 2, 10, 2, 3, 1, 0, 20 ); $k = 4; $sum = 18; $n = count ( $arr ); if (checkSubarraySum( $arr , $n , $k , $sum )) echo "YES" ; else echo "NO" ; // This code is contributed // by inder_verma ?> |
Javascript
<script> // Javascript program to check if any // Subarray of size K has a given Sum // Function to check if any Subarray // of size K has a given Sum function checkSubarraySum(arr, n, k, sum) { // Check for first window let curr_sum = 0; for (let i = 0; i < k; i++) curr_sum += arr[i]; if (curr_sum == sum) return true ; // Consider remaining blocks // ending with j for (let j = k; j < n; j++) { curr_sum = curr_sum + arr[j] - arr[j - k]; if (curr_sum == sum) return true ; } return false ; } // Driver code let arr = new Array( 1, 4, 2, 10, 2, 3, 1, 0, 20 ); let k = 4; let sum = 18; let n = arr.length; if (checkSubarraySum(arr, n, k, sum)) document.write( "YES" ); else document.write( "NO" ); // This code is contributed // by _saurabh_jaiswal </script> |
输出：
YES
时间复杂性 ：O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
