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

2021年3月17日18:07:56 发表评论 782 次浏览

## 本文概述

``````Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4
Sum of elements between indices
2 and 4 is 20 + 3 + 10 = 33

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4
Sum of elements between indices
1 and 4 is 4 + 0 + 0 + 3 = 7

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
There is no subarray with 0 sum``````

## 推荐：请在"实践首先, 在继续解决方案之前。

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 1

if curr_sum > sum or j = = n:
break

curr_sum = curr_sum + arr[j]
j + = 1

print ( "No subarray found" )
return 0

# Driver program
arr = [ 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 ]
n = len (arr)
sum = 23

subArraySum(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
?>``````

``Sum found between indexes 1 and 4``

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

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

# 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

# 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 = 23

subArraySum(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;
}

// 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(处理负数)
• 查找具有给定总和且在恒定空间中允许有负数的子数组