算法设计：总和大于给定值的最小子数组

2021年3月17日15:14:10 发表评论 809 次浏览

本文概述

给定整数数组和数字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)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: