本文概述
给定整数数组和数字x, 找到总和大于给定值的最小子数组。
Examples:
arr[] = {1, 4, 45, 6, 0, 19}
x = 51
Output: 3
Minimum length subarray is {4, 45, 6}
arr[] = {1, 10, 5, 2, 7}
x = 9
Output: 1
Minimum length subarray is {10}
arr[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}
x = 280
Output: 4
Minimum length subarray is {100, 1, 0, 200}
arr[] = {1, 2, 4}
x = 8
Output : Not Possible
Whole 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
?>
输出如下:
3
1
4
时间复杂度:上述方法的时间复杂度显然为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 x
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)
{
// 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 + = 1
return 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
?>
输出如下:
3
1
4
如何处理负数?
如果输入数组包含负数, 则上述解决方案可能不起作用。例如arr [] = {-8, 1, 4, 2, -6}。要处理负数, 请添加条件以忽略具有负和的子数组。我们可以使用在中讨论的解决方案
查找具有给定总和且在恒定空间中允许有负数的子数组
询问:脸书
本文作者:拉胡尔·贾恩(Rahul Jain)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。