本文概述

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

给定一个非排序的非负整数数组, 找到一个连续的子数组, 该数组加到给定的数字上。
例子 ：

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33Ouptut: Sum found between indexes 2 and 4Sum of elements between indices2 and 4 is 20 + 3 + 10 = 33Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7Ouptut: Sum found between indexes 1 and 4Sum of elements between indices1 and 4 is 4 + 0 + 0 + 3 = 7Input: arr[] = {1, 4}, sum = 0Output: No subarray foundThere is no subarray with 0 sum

可能有多个子数组, 且sum为给定的sum。以下解决方案将首先打印此类子数组。
推荐：请在"实践首先, 在继续解决方案之前。
简单方法：一个简单的解决方案是一个一个地考虑所有子阵列, 并检查每个子阵列的总和。以下程序实现简单的解决方案。运行两个循环：外部循环选择起点I, 内部循环尝试从i开始的所有子数组。
算法：

1. 从头到尾遍历数组。
2. 从每个索引开始另一个循环一世到数组的末尾以获取从i开始的所有子数组, 请保留一个变量总和以计算总和。
3. 对于内循环中的每个索引更新sum = sum +数组[j]
4. 如果总和等于给定的总和, 则打印子数组。

C ++

/* A simple program to print subarray with sum as given sum */ #include < bits/stdc++.h> using namespace std; /* Returns true if the there is a subarray of arr[] with sum equal to 'sum' otherwise returns false. Also, prints the result */ int subArraySum( int arr[], int n, int sum) { int curr_sum, i, j; // Pick a starting point for (i = 0; i < n; i++) { curr_sum = arr[i]; // try all subarrays starting with 'i' for (j = i + 1; j < = n; j++) { if (curr_sum == sum) { cout < < "Sum found between indexes " < < i < < " and " < < j - 1; return 1; } if (curr_sum > sum || j == n) break ; curr_sum = curr_sum + arr[j]; } }cout < < "No subarray found" ; return 0; }// Driver Code int main() { int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 }; int n = sizeof (arr) / sizeof (arr[0]); int sum = 23; subArraySum(arr, n, sum); return 0; }// This code is contributed // by rathbhupendra

C

/* A simple program to print subarray with sum as given sum */ #include < stdio.h> /* Returns true if the there is a subarray of arr[] with a sum equal to 'sum' otherwise returns false.Also, prints the result */ int subArraySum( int arr[], int n, int sum) { int curr_sum, i, j; // Pick a starting point for (i = 0; i < n; i++) { curr_sum = arr[i]; // try all subarrays starting with 'i' for (j = i + 1; j < = n; j++) { if (curr_sum == sum) { printf ( "Sum found between indexes %d and %d" , i, j - 1); return 1; } if (curr_sum > sum || j == n) break ; curr_sum = curr_sum + arr[j]; } }printf ( "No subarray found" ); return 0; }// Driver program to test above function int main() { int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 }; int n = sizeof (arr) / sizeof (arr[0]); int sum = 23; subArraySum(arr, n, sum); return 0; }

Java

class SubarraySum { /* Returns true if the there is a subarray of arr[] with a sum equal to 'sum' otherwise returns false. Also, prints the result */ int subArraySum( int arr[], int n, int sum) { int curr_sum, i, j; // Pick a starting point for (i = 0 ; i < n; i++) { curr_sum = arr[i]; // try all subarrays starting with 'i' for (j = i + 1 ; j < = n; j++) { if (curr_sum == sum) { int p = j - 1 ; System.out.println( "Sum found between indexes " + i + " and " + p); return 1 ; } if (curr_sum > sum || j == n) break ; curr_sum = curr_sum + arr[j]; } }System.out.println( "No subarray found" ); return 0 ; }public static void main(String[] args) { SubarraySum arraysum = new SubarraySum(); int arr[] = { 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 }; int n = arr.length; int sum = 23 ; arraysum.subArraySum(arr, n, sum); } }// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Returns true if the # there is a subarray # of arr[] with sum # equal to 'sum' # otherwise returns # false. Also, prints # the result def subArraySum(arr, n, sum ):# Pick a starting # point for i in range (n): curr_sum = arr[i]# try all subarrays # starting with 'i' j = i + 1 while j < = n:if curr_sum = = sum : print ( "Sum found between" ) print ( "indexes % d and % d" % ( i, j - 1 ))return 1if curr_sum > sum or j = = n: breakcurr_sum = curr_sum + arr[j] j + = 1print ( "No subarray found" ) return 0# Driver program arr = [ 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 ] n = len (arr) sum = 23subArraySum(arr, n, sum )# This code is Contributed by shreyanshi_arun.

C#

// C# code to Find subarray // with given sum using System; class GFG { // Returns true if the there is a // subarray of arr[] with sum // equal to 'sum' otherwise returns // false. Also, prints the result int subArraySum( int [] arr, int n, int sum) { int curr_sum, i, j; // Pick a starting point for (i = 0; i < n; i++) { curr_sum = arr[i]; // try all subarrays // starting with 'i' for (j = i + 1; j < = n; j++) { if (curr_sum == sum) { int p = j - 1; Console.Write( "Sum found between " + "indexes " + i + " and " + p); return 1; } if (curr_sum > sum || j == n) break ; curr_sum = curr_sum + arr[j]; } }Console.Write( "No subarray found" ); return 0; }// Driver Code public static void Main() { GFG arraysum = new GFG(); int [] arr = { 15, 2, 4, 8, 9, 5, 10, 23 }; int n = arr.Length; int sum = 23; arraysum.subArraySum(arr, n, sum); } }// This code has been contributed // by nitin mittal

的PHP

< ?php // A simple program to print subarray // with sum as given sum /* Returns true if the there is a subarray of arr[] with sum equal to 'sum' otherwise returns false. Also, prints the result */ function subArraySum( $arr , $n , $sum ) { $curr_sum ; $i ; $j ; // Pick a starting point for ( $i = 0; $i < $n ; $i ++) { $curr_sum = $arr [ $i ]; // try all subarrays // starting with 'i' for ( $j = $i + 1; $j < = $n ; $j ++) { if ( $curr_sum == $sum ) { echo "Sum found between indexes " , $i , " and " , $j -1 ; return 1; } if ( $curr_sum > $sum || $j == $n ) break ; $curr_sum = $curr_sum + $arr [ $j ]; } }echo "No subarray found" ; return 0; }// Driver Code $arr = array (15, 2, 4, 8, 9, 5, 10, 23); $n = sizeof( $arr ); $sum = 23; subArraySum( $arr , $n , $sum ); return 0; // This code is contributed by AJit ?>

【算法设计（查找给定总和的子数组|S1（非负实数））】输出：

Sum found between indexes 1 and 4

复杂度分析：

• 时间复杂度：O(n ^ 2)在最坏的情况下。
  嵌套循环用于遍历数组, 因此时间复杂度为O(n ^ 2)
• 空间复杂度：O(1)。
  由于需要恒定的额外空间。

高效方法：有一个想法, 如果数组的所有元素都是正的。如果子数组的总和大于给定的总和, 则不可能将元素添加到当前子数组中, 总和为X(给定的总和)。想法是对滑动窗口使用类似的方法。从一个空的子数组开始, 向该子数组添加元素, 直到总和小于X。如果总和大于X, 从当前子数组的开头删除元素。
算法：

1. 创建三个变量, l = 0, 总和= 0
2. 从头到尾遍历数组。
3. 通过添加当前元素来更新变量总和, 总和=总和+数组[i]
4. 如果总和大于给定总和, 则将变量总和更新为sum = sum –数组[l], 并将l更新为l ++。
5. 如果总和等于给定总和, 则打印子数组并中断循环。

C ++

/* An efficient program to print subarray with sum as given sum */ #include < iostream> using namespace std; /* Returns true if the there is a subarray of arr[] with a sum equal to 'sum' otherwise returns false. Also, prints the result */ int subArraySum( int arr[], int n, int sum) { /* Initialize curr_sum as value of first element and starting point as 0 */ int curr_sum = arr[0], start = 0, i; /* Add elements one by one to curr_sum and if the curr_sum exceeds the sum, then remove starting element */ for (i = 1; i < = n; i++) { // If curr_sum exceeds the sum, // then remove the starting elements while (curr_sum > sum & & start < i - 1) { curr_sum = curr_sum - arr[start]; start++; }// If curr_sum becomes equal to sum, // then return true if (curr_sum == sum) { cout < < "Sum found between indexes " < < start < < " and " < < i - 1; return 1; }// Add this element to curr_sum if (i < n) curr_sum = curr_sum + arr[i]; }// If we reach here, then no subarray cout < < "No subarray found" ; return 0; }// Driver Code int main() { int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 }; int n = sizeof (arr) / sizeof (arr[0]); int sum = 23; subArraySum(arr, n, sum); return 0; }// This code is contributed by SHUBHAMSINGH10

C

/* An efficient program to print subarray with sum as given sum */ #include < stdio.h> /* Returns true if the there is a subarray of arr[] with a sum equal to 'sum' otherwise returns false.Also, prints the result */ int subArraySum( int arr[], int n, int sum) { /* Initialize curr_sum as value of first element and starting point as 0 */ int curr_sum = arr[0], start = 0, i; /* Add elements one by one to curr_sum and if the curr_sum exceeds the sum, then remove starting element */ for (i = 1; i < = n; i++) { // If curr_sum exceeds the sum, // then remove the starting elements while (curr_sum > sum & & start < i - 1) { curr_sum = curr_sum - arr[start]; start++; }// If curr_sum becomes equal to sum, // then return true if (curr_sum == sum) { printf ( "Sum found between indexes %d and %d" , start, i - 1); return 1; }// Add this element to curr_sum if (i < n) curr_sum = curr_sum + arr[i]; }// If we reach here, then no subarray printf ( "No subarray found" ); return 0; }// Driver program to test above function int main() { int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 }; int n = sizeof (arr) / sizeof (arr[0]); int sum = 23; subArraySum(arr, n, sum); return 0; }

Java

class SubarraySum { /* Returns true if the there is a subarray of arr[] with sum equal to 'sum' otherwise returns false. Also, prints the result */ int subArraySum( int arr[], int n, int sum) { int curr_sum = arr[ 0 ], start = 0 , i; // Pick a starting point for (i = 1 ; i < = n; i++) { // If curr_sum exceeds the sum, // then remove the starting elements while (curr_sum > sum & & start < i - 1 ) { curr_sum = curr_sum - arr[start]; start++; }// If curr_sum becomes equal to sum, // then return true if (curr_sum == sum) { int p = i - 1 ; System.out.println( "Sum found between indexes " + start + " and " + p); return 1 ; }// Add this element to curr_sum if (i < n) curr_sum = curr_sum + arr[i]; }System.out.println( "No subarray found" ); return 0 ; }public static void main(String[] args) { SubarraySum arraysum = new SubarraySum(); int arr[] = { 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 }; int n = arr.length; int sum = 23 ; arraysum.subArraySum(arr, n, sum); } }// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# An efficient program # to print subarray # with sum as given sum # Returns true if the # there is a subarray # of arr[] with sum # equal to 'sum' # otherwise returns # false. Also, prints # the result. def subArraySum(arr, n, sum ):# Initialize curr_sum as # value of first element # and starting point as 0 curr_sum = arr[ 0 ] start = 0# Add elements one by # one to curr_sum and # if the curr_sum exceeds # the sum, then remove # starting element i = 1 while i < = n:# If curr_sum exceeds # the sum, then remove # the starting elements while curr_sum > sum and start < i - 1 :curr_sum = curr_sum - arr[start] start + = 1# If curr_sum becomes # equal to sum, then # return true if curr_sum = = sum : print ( "Sum found between indexes" ) print ( "% d and % d" % (start, i - 1 )) return 1# Add this element # to curr_sum if i < n: curr_sum = curr_sum + arr[i] i + = 1# If we reach here, # then no subarray print ( "No subarray found" ) return 0# Driver program arr = [ 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 ] n = len (arr) sum = 23subArraySum(arr, n, sum )# This code is Contributed by shreyanshi_arun.

C#

// An efficient C# program to print // subarray with sum as given sum using System; class GFG {// Returns true if the // there is a subarray of // arr[] with sum equal to // 'sum' otherwise returns false. // Also, prints the result int subArraySum( int [] arr, int n, int sum) { int curr_sum = arr[0], start = 0, i; // Pick a starting point for (i = 1; i < = n; i++) { // If curr_sum exceeds // the sum, then remove // the starting elements while (curr_sum > sum & & start < i - 1) { curr_sum = curr_sum - arr[start]; start++; }// If curr_sum becomes equal to // sum, then return true if (curr_sum == sum) { int p = i - 1; Console.WriteLine( "Sum found between " + "indexes " + start + " and " + p); return 1; }// Add this element to curr_sum if (i < n) curr_sum = curr_sum + arr[i]; } Console.WriteLine( "No subarray found" ); return 0; }// Driver code public static void Main() { GFG arraysum = new GFG(); int [] arr = new int [] { 15, 2, 4, 8, 9, 5, 10, 23 }; int n = arr.Length; int sum = 23; arraysum.subArraySum(arr, n, sum); } }// This code has been contributed by KRV.

的PHP

< ?php /* An efficient program to print subarray with sum as given sum *//* Returns true if the there is a subarray of arr[] with sum equal to 'sum' otherwise returns false. Also, prints the result */ function subArraySum( $arr , $n , $sum ) { /* Initialize curr_sum as value of first element and starting point as 0 */ $curr_sum = $arr [0]; $start = 0; $i ; /* Add elements one by one to curr_sum and if the curr_sum exceeds the sum, then remove starting element */ for ( $i = 1; $i < = $n ; $i ++) { // If curr_sum exceeds the sum, // then remove the starting elements while ( $curr_sum > $sum and $start < $i - 1) { $curr_sum = $curr_sum - $arr [ $start ]; $start ++; }// If curr_sum becomes equal // to sum, then return true if ( $curr_sum == $sum ) { echo "Sum found between indexes" , " " , $start , " " , "and " , " " , $i - 1; return 1; }// Add this element // to curr_sum if ( $i < $n ) $curr_sum = $curr_sum + $arr [ $i ]; }// If we reach here, // then no subarray echo "No subarray found" ; return 0; }// Driver Code $arr = array (15, 2, 4, 8, 9, 5, 10, 23); $n = count ( $arr ); $sum = 23; subArraySum( $arr , $n , $sum ); // This code has been // contributed by anuj_67. ?>

输出：

Sum found between indexes 1 and 4

复杂度分析：

• 时间复杂度：上)。
  只需要遍历数组一次。因此, 时间复杂度为O(n)。
• 空间复杂度：O(1)。
  由于需要恒定的额外空间。

上述解决方案无法处理负数。我们可以使用哈希处理负数。请参阅下面的第2组。

• 查找给定总和的子数组|设置2(处理负数)
• 查找具有给定总和且在恒定空间中允许有负数的子数组

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  脆柿就是还没熟的柿子吗
• 

  if else if理解订正
• 

  安卓单机游戏排行榜前十名手游，安卓手机有哪些游戏好玩 单机的
• 

  《锦瑟》最后一联表达了诗人什么样的思想情感？
• 

  有纹身的女人才是最性感的
• 

  腊八节民间有哪些传统习俗 腊八节有什么传统文化
• 

  婚姻一方精神病可以离婚吗
• 

  形容下雨天心情不好的句子
• 

  隔夜稀饭怎么会变粉色
• 

  雪梨银耳汤做法有哪些 银耳雪梨猪手汤怎么制作
• 

  癌症|2020中国十大高发癌症｜世界癌症日
• 

  朝加偏旁组词 朝加偏旁到底能组成啥字呢
• 

  qq看点免流量吗? QQ怎么查看免流量特权
• 

  gta5中文字幕怎么设置
• 

  php加密客户端数据加密 php加密后怎么运行
• 

  在试用期内辞职随时能拿到工资吗
• 

  哪种天气情况下瓜果会甜一些
• 

  高德地图怎么叫车？
• 

  枪神2，枪神2目前使用的人多吗能不能评价一下
• 

  童年第十章主要内容 童年简介

• Python在list中的替代元素求和
• 深度win7旗舰版32位最新系统推荐
• win764位系统装32位系统图文详细教程图解
• 装机高手教你如何在win10下重装win8.1
• win7 64位纯净版硬盘安装图文详细教程图解
• 装机高手教你win7 32位与64选择哪个好?
• 32win7装64win7图文详细教程图解
• win7安装版步骤图文详细教程图解
• 系统之家U盘制作工具装win732位图文详细教程图解