总和大于给定值的最小子数组
原文： https://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/
给定一个整数数组和一个数字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(n^2)。
有效解决方案：可以使用此帖子中的想法，在O(n)时间中解决此问题。 感谢 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}。 要处理负数，请添加条件以忽略具有负和的子数组。 我们可以使用在恒定空间中查找具有给定总和且允许有负数的子数组中讨论的解决方案。
版权属于：月萌API www.moonapi.com，转载请注明出处
