总和大于给定值的最小子数组 · GeeksForGeeks 中文系列教程

# 总和大于给定值的最小子数组 > 原文： [https://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/](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 ```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 ```py # 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# ```cs // 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 <?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)`。 **有效解决方案**：可以使用[此](https://www.geeksforgeeks.org/find-subarray-with-given-sum/)帖子中的想法，在 **`O(n)`时间**中解决此问题。感谢 Ankit 和 Nitin 提出这个优化的解决方案。 ## C++ ```cpp // 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; } ```