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

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

本文概述

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

例子 ：

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

可能有多个子数组, 且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 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)。
    由于需要恒定的额外空间。

高效方法：有一个想法, 如果数组的所有元素都是正的。如果子数组的总和大于给定的总和, 则不可能将元素添加到当前子数组中, 总和为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 = 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;
         }
  
         // 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(处理负数)
  • 查找具有给定总和且在恒定空间中允许有负数的子数组

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: