本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• C
• Java
• Python3
• C#
• 的PHP
• C ++
• Java
• Python3
• C#
• 的PHP

给定整数数组和数字x, 找到总和大于给定值的最小子数组。

Examples:arr[] = {1, 4, 45, 6, 0, 19}x=51Output: 3Minimum length subarray is {4, 45, 6}arr[] = {1, 10, 5, 2, 7}x= 9Output: 1Minimum length subarray is {10}arr[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}x = 280Output: 4Minimum length subarray is {100, 1, 0, 200}arr[] = {1, 2, 4}x = 8Output : Not PossibleWhole array sum is smaller than 8.

推荐：请在"实践首先, 在继续解决方案之前。一种
简单的解决方案
是使用两个嵌套循环。外循环选择一个开始元素, 内循环将所有元素(在当前开始的右侧)视为结束元素。只要当前开始和结束之间的元素总数超过给定数目, 如果当前长度小于到目前为止的最小长度, 则更新结果。
以下是简单方法的实现。
C

# include < iostream> using namespace std; // Returns length of smallest subarray with sum greater than x. // If there is no subarray with given sum, then returns n+1 int smallestSubWithSum( int arr[], int n, int x) { //Initilize length of smallest subarray as n+1 int min_len = n + 1; // Pick every element as starting point for ( int start=0; start< n; start++) { // Initialize sum starting with current start int curr_sum = arr[start]; // If first element itself is greater if (curr_sum > x) return 1; // Try different ending points for curremt start for ( int end=start+1; end< n; end++) { // add last element to current sum curr_sum += arr[end]; // If sum becomes more than x and length of // this subarray is smaller than current smallest // length, update the smallest length (or result) if (curr_sum > x & & (end - start + 1) < min_len) min_len = (end - start + 1); } } return min_len; }/* Driver program to test above function */ int main() { int arr1[] = {1, 4, 45, 6, 10, 19}; int x = 51; int n1 = sizeof (arr1)/ sizeof (arr1[0]); int res1 = smallestSubWithSum(arr1, n1, x); (res1 == n1+1)? cout < < "Not possible\n" : cout < < res1 < < endl; int arr2[] = {1, 10, 5, 2, 7}; int n2 = sizeof (arr2)/ sizeof (arr2[0]); x= 9; int res2 = smallestSubWithSum(arr2, n2, x); (res2 == n2+1)? cout < < "Not possible\n" : cout < < res2 < < endl; int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}; int n3 = sizeof (arr3)/ sizeof (arr3[0]); x= 280; int res3 = smallestSubWithSum(arr3, n3, x); (res3 == n3+1)? cout < < "Not possible\n" : cout < < res3 < < endl; return 0; }

Java

class SmallestSubArraySum { // Returns length of smallest subarray with sum greater than x. // If there is no subarray with given sum, then returns n+1 static int smallestSubWithSum( int arr[], int n, int x) { //Initilize length of smallest subarray as n+1 int min_len = n + 1 ; // Pick every element as starting point for ( int start = 0 ; start < n; start++) { // Initialize sum starting with current start int curr_sum = arr[start]; // If first element itself is greater if (curr_sum > x) return 1 ; // Try different ending points for curremt start for ( int end = start + 1 ; end < n; end++) { // add last element to current sum curr_sum += arr[end]; // If sum becomes more than x and length of // this subarray is smaller than current smallest // length, update the smallest length (or result) if (curr_sum > x & & (end - start + 1 ) < min_len) min_len = (end - start + 1 ); } } return min_len; }// Driver program to test above functions public static void main(String[] args) { int arr1[] = { 1 , 4 , 45 , 6 , 10 , 19 }; int x = 51 ; int n1 = arr1.length; int res1 = smallestSubWithSum(arr1, n1, x); if (res1 == n1+ 1 ) System.out.println( "Not Possible" ); else System.out.println(res1); int arr2[] = { 1 , 10 , 5 , 2 , 7 }; int n2 = arr2.length; x = 9 ; int res2 = smallestSubWithSum(arr2, n2, x); if (res2 == n2+ 1 ) System.out.println( "Not Possible" ); else System.out.println(res2); int arr3[] = { 1 , 11 , 100 , 1 , 0 , 200 , 3 , 2 , 1 , 250 }; int n3 = arr3.length; x = 280 ; int res3 = smallestSubWithSum(arr3, n3, x); if (res3 == n3+ 1 ) System.out.println( "Not Possible" ); else System.out.println(res3); } }// This code has been contributed by Mayank Jaiswal

Python3

# Python3 program to find Smallest # subarray with sum greater # than a given value# Returns length of smallest subarray # with sum greater than x. If there # is no subarray with given sum, # then returns n+1 def smallestSubWithSum(arr, n, x):# Initilize length of smallest # subarray as n+1 min_len = n + 1# Pick every element as starting point for start in range ( 0 , n):# Initialize sum starting # with current start curr_sum = arr[start]# If first element itself is greater if (curr_sum > x): return 1# Try different ending points # for curremt start for end in range (start + 1 , n):# add last element to current sum curr_sum + = arr[end]# If sum becomes more than x # and length of this subarray # is smaller than current smallest # length, update the smallest # length (or result) if curr_sum > x and (end - start + 1 ) < min_len: min_len = (end - start + 1 )return min_len; # Driver program to test above function */ arr1 = [ 1 , 4 , 45 , 6 , 10 , 19 ] x = 51 n1 = len (arr1) res1 = smallestSubWithSum(arr1, n1, x); if res1 = = n1 + 1 : print ( "Not possible" ) else : print (res1)arr2 = [ 1 , 10 , 5 , 2 , 7 ] n2 = len (arr2) x = 9 res2 = smallestSubWithSum(arr2, n2, x); if res2 = = n2 + 1 : print ( "Not possible" ) else : print (res2)arr3 = [ 1 , 11 , 100 , 1 , 0 , 200 , 3 , 2 , 1 , 250 ] n3 = len (arr3) x = 280 res3 = smallestSubWithSum(arr3, n3, x) if res3 = = n3 + 1 : print ( "Not possible" ) else : print (res3)# This code is contributed by Smitha Dinesh Semwal

C#

// C# program to find Smallest // subarray with sum greater // than a given value using System; class GFG {// Returns length of smallest // subarray with sum greater // than x. If there is no // subarray with given sum, // then returns n+1 static int smallestSubWithSum( int []arr, int n, int x) { // Initilize length of // smallest subarray as n+1 int min_len = n + 1; // Pick every element // as starting point for ( int start = 0; start < n; start++) { // Initialize sum starting // with current start int curr_sum = arr[start]; // If first element // itself is greater if (curr_sum > x) return 1; // Try different ending // points for curremt start for ( int end = start + 1; end < n; end++) { // add last element // to current sum curr_sum += arr[end]; // If sum becomes more than // x and length of this // subarray is smaller than // current smallest length, // update the smallest // length (or result) if (curr_sum > x & & (end - start + 1) < min_len) min_len = (end - start + 1); } } return min_len; }// Driver Code static public void Main () { int []arr1 = {1, 4, 45, 6, 10, 19}; int x = 51; int n1 = arr1.Length; int res1 = smallestSubWithSum(arr1, n1, x); if (res1 == n1 + 1) Console.WriteLine( "Not Possible" ); else Console.WriteLine(res1); int []arr2 = {1, 10, 5, 2, 7}; int n2 = arr2.Length; x = 9; int res2 = smallestSubWithSum(arr2, n2, x); if (res2 == n2 + 1) Console.WriteLine( "Not Possible" ); else Console.WriteLine(res2); int []arr3 = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}; int n3 = arr3.Length; x = 280; int res3 = smallestSubWithSum(arr3, n3, x); if (res3 == n3 + 1) Console.WriteLine( "Not Possible" ); else Console.WriteLine(res3); } }// This code is contributed by ajit

的PHP

< ?php // Returns length of smallest // subarray with sum greater // than x. If there is no // subarray with given sum, // then returns n+1 function smallestSubWithSum( $arr , $n , $x ) { // Initilize length of // smallest subarray as n+1 $min_len = $n + 1; // Pick every element // as starting point for ( $start = 0; $start < $n ; $start ++) { // Initialize sum starting // with current start $curr_sum = $arr [ $start ]; // If first element // itself is greater if ( $curr_sum > $x ) return 1; // Try different ending // points for curremt start for ( $end = $start + 1; $end < $n ; $end ++) { // add last element // to current sum $curr_sum += $arr [ $end ]; // If sum becomes more than // x and length of this subarray // is smaller than current // smallest length, update the // smallest length (or result) if ( $curr_sum > $x & & ( $end - $start + 1) < $min_len ) $min_len = ( $end - $start + 1); } } return $min_len ; }// Driver Code $arr1 = array (1, 4, 45, 6, 10, 19); $x = 51; $n1 = sizeof( $arr1 ); $res1 = smallestSubWithSum( $arr1 , $n1 , $x ); if (( $res1 == $n1 + 1) == true) echo "Not possible\n" ; else echo $res1 , "\n" ; $arr2 = array (1, 10, 5, 2, 7); $n2 = sizeof( $arr2 ); $x = 9; $res2 = smallestSubWithSum( $arr2 , $n2 , $x ); if (( $res2 == $n2 + 1) == true) echo "Not possible\n" ; else echo $res2 , "\n" ; $arr3 = array (1, 11, 100, 1, 0, 200, 3, 2, 1, 250); $n3 = sizeof( $arr3 ); $x = 280; $res3 = smallestSubWithSum( $arr3 , $n3 , $x ); if (( $res3 == $n3 + 1) == true) echo "Not possible\n" ; else echo $res3 , "\n" ; // This code is contributed by ajit ?>

输出如下：

314

【算法设计（总和大于给定值的最小子数组）】时间复杂度：上述方法的时间复杂度显然为O(n2)。
高效的解决方案：
这个问题可以解决
准时
使用的想法
这个
发布。感谢Ankit和Nitin提出这个优化的解决方案。
C ++

// O(n) solution for finding smallest subarray with sum // greater than x #include < iostream> using namespace std; // Returns length of smallest subarray with sum greater than x. // If there is no subarray with given sum, then returns n+1 int smallestSubWithSum( int arr[], int n, int x) { // Initialize current sum and minimum length int curr_sum = 0, min_len = n+1; // Initialize starting and ending indexes int start = 0, end = 0; while (end < n) { // Keep adding array elements while current sum // is smaller than x while (curr_sum < = x & & end < n) curr_sum += arr[end++]; // If current sum becomes greater than x. while (curr_sum > x & & start < n) { // Update minimum length if needed if (end - start < min_len) min_len = end - start; // remove starting elements curr_sum -= arr[start++]; } } return min_len; }/* Driver program to test above function */ int main() { int arr1[] = {1, 4, 45, 6, 10, 19}; int x = 51; int n1 = sizeof (arr1)/ sizeof (arr1[0]); int res1 = smallestSubWithSum(arr1, n1, x); (res1 == n1+1)? cout < < "Not possible\n" : cout < < res1 < < endl; int arr2[] = {1, 10, 5, 2, 7}; int n2 = sizeof (arr2)/ sizeof (arr2[0]); x= 9; int res2 = smallestSubWithSum(arr2, n2, x); (res2 == n2+1)? cout < < "Not possible\n" : cout < < res2 < < endl; int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}; int n3 = sizeof (arr3)/ sizeof (arr3[0]); x= 280; int res3 = smallestSubWithSum(arr3, n3, x); (res3 == n3+1)? cout < < "Not possible\n" : cout < < res3 < < endl; return 0; }

Java

// O(n) solution for finding smallest subarray with sum // greater than xclass SmallestSubArraySum { // Returns length of smallest subarray with sum greater than x. // If there is no subarray with given sum, then returns n+1 static int smallestSubWithSum( int arr[], int n, int x) { // Initialize current sum and minimum length int curr_sum = 0 , min_len = n + 1 ; // Initialize starting and ending indexes int start = 0 , end = 0 ; while (end < n) { // Keep adding array elements while current sum // is smaller than x while (curr_sum < = x & & end < n) curr_sum += arr[end++]; // If current sum becomes greater than x. while (curr_sum > x & & start < n) { // Update minimum length if needed if (end - start < min_len) min_len = end - start; // remove starting elements curr_sum -= arr[start++]; } } return min_len; } // Driver program to test above functions public static void main(String[] args) { int arr1[] = { 1 , 4 , 45 , 6 , 10 , 19 }; int x = 51 ; int n1 = arr1.length; int res1 = smallestSubWithSum(arr1, n1, x); if (res1 == n1+ 1 ) System.out.println( "Not Possible" ); else System.out.println(res1); int arr2[] = { 1 , 10 , 5 , 2 , 7 }; int n2 = arr2.length; x = 9 ; int res2 = smallestSubWithSum(arr2, n2, x); if (res2 == n2+ 1 ) System.out.println( "Not Possible" ); else System.out.println(res2); int arr3[] = { 1 , 11 , 100 , 1 , 0 , 200 , 3 , 2 , 1 , 250 }; int n3 = arr3.length; x = 280 ; int res3 = smallestSubWithSum(arr3, n3, x); if (res3 == n3+ 1 ) System.out.println( "Not Possible" ); else System.out.println(res3); } }// This code has been contributed by Mayank Jaiswal

Python3

# O(n) solution for finding smallest # subarray with sum greater than x# Returns length of smallest subarray # with sum greater than x. If there # is no subarray with given sum, then # returns n + 1 def smallestSubWithSum(arr, n, x):# Initialize current sum and minimum length curr_sum = 0 min_len = n + 1# Initialize starting and ending indexes start = 0 end = 0 while (end < n):# Keep adding array elements while current # sum is smaller than x while (curr_sum < = x and end < n): curr_sum + = arr[end] end + = 1# If current sum becomes greater than x. while (curr_sum > x and start < n):# Update minimum length if needed if (end - start < min_len): min_len = end - start # remove starting elements curr_sum - = arr[start] start + = 1return min_len # Driver program arr1 = [ 1 , 4 , 45 , 6 , 10 , 19 ] x = 51 n1 = len (arr1) res1 = smallestSubWithSum(arr1, n1, x) print ( "Not possible" ) if (res1 = = n1 + 1 ) else print (res1) arr2 = [ 1 , 10 , 5 , 2 , 7 ] n2 = len (arr2) x = 9 res2 = smallestSubWithSum(arr2, n2, x) print ( "Not possible" ) if (res2 = = n2 + 1 ) else print (res2) arr3 = [ 1 , 11 , 100 , 1 , 0 , 200 , 3 , 2 , 1 , 250 ] n3 = len (arr3) x = 280 res3 = smallestSubWithSum(arr3, n3, x) print ( "Not possible" ) if (res3 = = n3 + 1 ) else print (res3) # This code is contributed by # Smitha Dinesh Semwal

C#

// O(n) solution for finding // smallest subarray with sum // greater than x using System; class GFG {// Returns length of smallest // subarray with sum greater // than x. If there is no // subarray with given sum, // then returns n+1 static int smallestSubWithSum( int []arr, int n, int x) { // Initialize current // sum and minimum length int curr_sum = 0, min_len = n + 1; // Initialize starting // and ending indexes int start = 0, end = 0; while (end < n) { // Keep adding array elements // while current sum is smaller // than x while (curr_sum < = x & & end < n) curr_sum += arr[end++]; // If current sum becomes // greater than x. while (curr_sum > x & & start < n) { // Update minimum // length if needed if (end - start < min_len) min_len = end - start; // remove starting elements curr_sum -= arr[start++]; } } return min_len; }// Driver Code static public void Main () { int []arr1 = {1, 4, 45, 6, 10, 19}; int x = 51; int n1 = arr1.Length; int res1 = smallestSubWithSum(arr1, n1, x); if (res1 == n1 + 1) Console.WriteLine( "Not Possible" ); else Console.WriteLine(res1); int []arr2 = {1, 10, 5, 2, 7}; int n2 = arr2.Length; x = 9; int res2 = smallestSubWithSum(arr2, n2, x); if (res2 == n2 + 1) Console.WriteLine( "Not Possible" ); else Console.WriteLine(res2); int []arr3 = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}; int n3 = arr3.Length; x = 280; int res3 = smallestSubWithSum(arr3, n3, x); if (res3 == n3 + 1) Console.WriteLine( "Not Possible" ); else Console.WriteLine(res3); } }// This code is contributed by akt_mit

的PHP

< ?php // O(n) solution for finding // smallest subarray with sum // greater than x// Returns length of smallest // subarray with sum greater // than x. If there is no // subarray with given sum, // then returns n+1 function smallestSubWithSum( $arr , $n , $x ) { // Initialize current // sum and minimum length $curr_sum = 0; $min_len = $n + 1; // Initialize starting // and ending indexes $start = 0; $end = 0; while ( $end < $n ) { // Keep adding array elements // while current sum is smaller // than x while ( $curr_sum < = $x & & $end < $n ) $curr_sum += $arr [ $end ++]; // If current sum becomes // greater than x. while ( $curr_sum > $x & & $start < $n ) { // Update minimum // length if needed if ( $end - $start < $min_len ) $min_len = $end - $start ; // remove starting elements $curr_sum -= $arr [ $start ++]; } } return $min_len ; }// Driver Code $arr1 = array (1, 4, 45, 6, 10, 19); $x = 51; $n1 = sizeof( $arr1 ); $res1 = smallestSubWithSum( $arr1 , $n1 , $x ); if ( $res1 == $n1 + 1) echo "Not possible\n" ; else echo $res1 , "\n" ; $arr2 = array (1, 10, 5, 2, 7); $n2 = sizeof( $arr2 ); $x = 9; $res2 = smallestSubWithSum( $arr2 , $n2 , $x ); if ( $res2 == $n2 + 1) echo "Not possible\n" ; else echo $res2 , "\n" ; $arr3 = array (1, 11, 100, 1, 0, 200, 3, 2, 1, 250); $n3 = sizeof( $arr3 ); $x = 280; $res3 = smallestSubWithSum( $arr3 , $n3 , $x ); if ( $res3 == $n3 + 1) echo "Not possible\n" ; else echo $res3 , "\n" ; // This code is contributed by ajit ?>

输出如下：

314

如何处理负数？
如果输入数组包含负数, 则上述解决方案可能不起作用。例如arr [] = {-8, 1, 4, 2, -6}。要处理负数, 请添加条件以忽略具有负和的子数组。我们可以使用在中讨论的解决方案
查找具有给定总和且在恒定空间中允许有负数的子数组
询问：脸书
本文作者：拉胡尔·贾恩(Rahul Jain)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  如何迅速去甲醛味 怎么快速去除甲醛味
• 

  linux挂载命令配置 linux挂载命令怎么理解
• 

  打完新冠疫苗能运动吗
• 

  家用烧烤怎么烤好吃 在家烧烤怎么烤好吃
• 

  sql 云 服务器 云服务器mysql中文
• 

  什么原因会导致乳腺增生呢！
• 

  微信欢乐球球怎么玩高分 微信欢乐球球全关卡高分技巧
• 

  关于增票遗失的问题
• 

  细子龙 细子龙图片
• 

  如何寻找玩字词游戏的时间！（原创日记83）
• 

  ultraedit找到对应括号 UltraEdit匹配大括号内容的具体方法讲解
• 

  空气洗衣洗衣机为什么会烫,用过的都会这样说
• 

  工程专业的妹子做什么工作比较好？
• 

  003 - windows api - Device Roles
• 

  小米|雷军憋大招！小米MIX4规格被曝光，屏下摄像头很惹眼
• 

  蛋糕的热量是多少
• 

  高雄旅游攻略 高雄哪里好玩
• 

  冬季护肤薏米食谱
• 

  我试过“权健火疗”，管用！真事！
• 

  猫和老鼠里面的汤姆猫是什么品种 汤姆猫是什么品种

• C语言中的NULL指针介绍和代码示例
• win8鼠标双击速度设置小技巧
• win8全屏截图自动保存至桌面的技巧
• win8文件视图一键同步设置技巧
• win8磁盘分区无法重命名的处理技巧
• 拒绝平庸！打造个性化Win8系统MetroQQ图标
• win8 24小时制设置的图文详细教程
• win8开机不输密码直接登录的好妙招
• win8系统容易的优化技巧