本文概述
- 建议:在继续解决方案之前, 请先在"实践"上解决它。
- 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开始的所有子数组。
算法:
- 从头到尾遍历数组。
- 从每个索引开始另一个循环一世到数组的末尾以获取从i开始的所有子数组, 请保留一个变量总和以计算总和。
- 对于内循环中的每个索引更新sum = sum +数组[j]
- 如果总和等于给定的总和, 则打印子数组。
/* 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)。
由于需要恒定的额外空间。
算法:
- 创建三个变量, l = 0, 总和= 0
- 从头到尾遍历数组。
- 通过添加当前元素来更新变量总和, 总和=总和+数组[i]
- 如果总和大于给定总和, 则将变量总和更新为sum = sum –数组[l], 并将l更新为l ++。
- 如果总和等于给定总和, 则打印子数组并中断循环。
/* 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(处理负数)
- 查找具有给定总和且在恒定空间中允许有负数的子数组
推荐阅读
- Python在list中的替代元素求和
- 深度win7旗舰版32位最新系统推荐
- win764位系统装32位系统图文详细教程图解
- 装机高手教你如何在win10下重装win8.1
- win7 64位纯净版硬盘安装图文详细教程图解
- 装机高手教你win7 32位与64选择哪个好?
- 32win7装64win7图文详细教程图解
- win7安装版步骤图文详细教程图解
- 系统之家U盘制作工具装win732位图文详细教程图解