查找具有给定和|集2（处理负数）的子数组-yiteyi-C++库

给定一个未排序的整数数组，找到一个子数组，将其与给定的数字相加。如果有多个子阵列具有给定数字的总和，请打印其中任何一个子阵列。

null

例如：

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33Output: Sum found between indexes 2 and 4Explanation: Sum of elements between indices2 and 4 is 20 + 3 + 10 = 33Input: arr[] = {10, 2, -2, -20, 10}, sum = -10Output: Sum found between indexes 0 to 3Explanation: Sum of elements between indices0 and 3 is 10 + 2 - 2 - 20 = -10Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20Output: No subarray with given sum existsExplanation: There is no subarray with the given sum

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

注：我们讨论了一个不处理负整数的解决方案在这里 .在这篇文章中，负整数也被处理。

简单方法： 一个简单的解决方案是逐个考虑所有子阵列并检查每个子阵列的和。下面的程序实现了这个简单的解决方案。运行两个循环：外循环选择起点I，内循环尝试从I开始的所有子数组。

算法：

从头到尾遍历阵列。
从每个索引开始从i到数组末尾的另一个循环，以获得从i开始的所有子数组，保留一个变量和来计算和。对于内部循环中的每个索引，更新sum=sum+array[j]如果和等于给定的和，则打印子数组。
对于内部循环中的每个索引，更新sum=sum+array[j]
如果和等于给定的和，则打印子阵列。

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 = 0;                       
                                   
                                                 // try all subarrays starting with 'i'                       
                                                 for                                     (j = i ; j < n; j++) {                       
                                                 curr_sum = curr_sum + arr[j];                       
                                   
                                                 if                                     (curr_sum == sum) {                       
                                                 cout <<                                     "Sum found between indexes "                       
                                                 << i <<                                     " and "                                     << j ;                       
                                                 return                                     1;                       
                                                 }                       
                                   
                                   
                                                 }                       
                                                 }                       
                                   
                                                 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;                       
                         }                       

JAVA

                         // Java program for the above approach                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         /* Returns true if the there is a subarray                       
                         of arr[] with sum equal to 'sum' otherwise                       
                         returns false. Also, prints the result */                       
                         static                                     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 =                                     0                                     ;                       
                                   
                                                 // try all subarrays starting with 'i'                       
                                                 for                                     (j = i ; j < n; j++) {                       
                                                 curr_sum = curr_sum + arr[j];                       
                                   
                                                 if                                     (curr_sum == sum) {                       
                                                 System.out.print(                                     "Sum found between indexes "                       
                                                 + i +                                     " and "                                     + j);                       
                                                 return                                     1                                     ;                       
                                                 }                       
                                   
                                   
                                                 }                       
                                                 }                       
                                   
                                                 System.out.print(                                     "No subarray found"                                     );                       
                                                 return                                     0                                     ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     arr[] = {                                     15                                     ,                                     2                                     ,                                     4                                     ,                                     8                                     ,                                     9                                     ,                                     5                                     ,                                     10                                     ,                                     23                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     sum =                                     23                                     ;                       
                                                 subArraySum(arr, n, sum);                       
                         }                       
                         }                       
           
                         // This code is contributed by code_hunt.                       

输出

Sum found between indexes 1 and 4

方法： 其思想是将数组中每个前缀的元素之和存储在一个hashmap中，即每个索引存储该索引hashmap之前的元素之和。所以要检查是否有一个子数组的和等于 s ，检查每个索引i，并将该索引汇总为十、 .如果有一个前缀的和等于 x–s ，然后找到具有给定和的子阵列。

算法：

创建一个Hashmap( 陛下 )存储键值对，即key=前缀和value=其索引，以及存储当前和的变量( 总和=0 )子数组的和为 s
从头到尾遍历阵列。
对于每个元素，更新总和，即 求和=求和+数组[i]
如果总和等于s，则打印出具有给定总和的子阵列从0到i
如果HashMap中有任何键等于 总和–s 然后打印具有给定和的子阵列是从hm[sum–s]到i
将总和和索引作为键值对放在hashmap中。

上述方法的试运行：

图片[1]-查找具有给定和|集2（处理负数）的子数组-yiteyi-C++库

实施：

C++

                         // C++ program to print subarray with sum as given sum                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to print subarray with sum as given sum                       
                         void                                     subArraySum(                                     int                                     arr[],                                     int                                     n,                                     int                                     sum)                       
                         {                       
                                                 // create an empty map                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > map;                       
           
                                                 // Maintains sum of elements so far                       
                                                 int                                     curr_sum = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // add current element to curr_sum                       
                                                 curr_sum = curr_sum + arr[i];                       
           
                                                 // if curr_sum is equal to target sum                       
                                                 // we found a subarray starting from index 0                       
                                                 // and ending at index i                       
                                                 if                                     (curr_sum == sum)                       
                                                 {                       
                                                 cout <<                                     "Sum found between indexes "                       
                                                 << 0 <<                                     " to "                                     << i << endl;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 // If curr_sum - sum already exists in map                       
                                                 // we have found a subarray with target sum                       
                                                 if                                     (map.find(curr_sum - sum) != map.end())                       
                                                 {                       
                                                 cout <<                                     "Sum found between indexes "                       
                                                 << map[curr_sum - sum] + 1                       
                                                 <<                                     " to "                                     << i << endl;                       
                                                 return                                     ;                       
                                                 }                       
           
                                                 map[curr_sum] = i;                       
                                                 }                       
           
                                                 // If we reach here, then no subarray exists                       
                                                 cout <<                                     "No subarray with given sum exists"                                     ;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {10, 2, -2, -20, 10};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 int                                     sum = -10;                       
           
                                                 subArraySum(arr, n, sum);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print subarray with sum as given sum                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 public                                     static                                     void                                     subArraySum(                                     int                                     [] arr,                                     int                                     n,                                     int                                     sum) {                       
                                                 //cur_sum to keep track of cumulative sum till that point                       
                                                 int                                     cur_sum =                                     0                                     ;                       
                                                 int                                     start =                                     0                                     ;                       
                                                 int                                     end = -                                     1                                     ;                       
                                                 HashMap<Integer, Integer> hashMap =                                     new                                     HashMap<>();                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 cur_sum = cur_sum + arr[i];                       
                                                 //check whether cur_sum - sum = 0, if 0 it means                       
                                                 //the sub array is starting from index 0- so stop                       
                                                 if                                     (cur_sum - sum ==                                     0                                     ) {                       
                                                 start =                                     0                                     ;                       
                                                 end = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 //if hashMap already has the value, means we already                       
                                                 // have subarray with the sum - so stop                       
                                                 if                                     (hashMap.containsKey(cur_sum - sum)) {                       
                                                 start = hashMap.get(cur_sum - sum) +                                     1                                     ;                       
                                                 end = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 //if value is not present then add to hashmap                       
                                                 hashMap.put(cur_sum, i);                       
           
                                                 }                       
                                                 // if end is -1 : means we have reached end without the sum                       
                                                 if                                     (end == -                                     1                                     ) {                       
                                                 System.out.println(                                     "No subarray with given sum exists"                                     );                       
                                                 }                                     else                                     {                       
                                                 System.out.println(                                     "Sum found between indexes "                       
                                                 + start +                                     " to "                                     + end);                       
                                                 }                       
           
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 int                                     [] arr = {                                     10                                     ,                                     2                                     , -                                     2                                     , -                                     20                                     ,                                     10                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     sum = -                                     10                                     ;                       
                                                 subArraySum(arr, n, sum);                       
           
                                                 }                       
                         }                       

Python3

                         # Python3 program to print subarray with sum as given sum                       
           
                         # Function to print subarray with sum as given sum                       
                         def                                     subArraySum(arr, n,                                     Sum                                     ):                       
                                   
                                                 # create an empty map                       
                                                 Map                                     =                                     {}                       
                                   
                                                 # Maintains sum of elements so far                       
                                                 curr_sum                                     =                                     0                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,n):                       
                                   
                                                 # add current element to curr_sum                       
                                                 curr_sum                                     =                                     curr_sum                                     +                                     arr[i]                       
                                   
                                                 # if curr_sum is equal to target sum                       
                                                 # we found a subarray starting from index 0                       
                                                 # and ending at index i                       
                                                 if                                     curr_sum                                     =                                     =                                     Sum                                     :                       
                                   
                                                 print                                     (                                     "Sum found between indexes 0 to"                                     , i)                       
                                                 return                       
                                   
                                   
                                                 # If curr_sum - sum already exists in map                       
                                                 # we have found a subarray with target sum                       
                                                 if                                     (curr_sum                                     -                                     Sum                                     )                                     in                                     Map                                     :                       
                                   
                                                 print                                     (                                     "Sum found between indexes"                                     ,                       
                                                 Map                                     [curr_sum                                     -                                     Sum                                     ]                                     +                                     1                                     ,                                     "to"                                     , i)                       
                                   
                                                 return                       
                                   
                                                 Map                                     [curr_sum]                                     =                                     i                       
                                   
                                                 # If we reach here, then no subarray exists                       
                                                 print                                     (                                     "No subarray with given sum exists"                                     )                       
                                   
                                   
                         # Driver program to test above function                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                   
                                                 arr                                     =                                     [                                     10                                     ,                                     2                                     ,                                     -                                     2                                     ,                                     -                                     20                                     ,                                     10                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 Sum                                     =                                     -                                     10                       
                                   
                                                 subArraySum(arr, n,                                     Sum                                     )                       
                                   
                         # This code is contributed by Rituraj Jain                       

C#

                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         // C# program to print subarray with sum as given sum                       
           
                         public                                     class                                     GFG                       
                         {                       
           
                                                 public                                     static                                     void                                     subArraySum(                                     int                                     [] arr,                                     int                                     n,                                     int                                     sum)                       
                                                 {                       
                                                 //cur_sum to keep track of cumulative sum till that point                       
                                                 int                                     cur_sum = 0;                       
                                                 int                                     start = 0;                       
                                                 int                                     end = -1;                       
                                                 Dictionary<                                     int                                     ,                                     int                                     > hashMap =                                     new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 cur_sum = cur_sum + arr[i];                       
                                                 //check whether cur_sum - sum = 0, if 0 it means                       
                                                 //the sub array is starting from index 0- so stop                       
                                                 if                                     (cur_sum - sum == 0)                       
                                                 {                       
                                                 start = 0;                       
                                                 end = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 //if hashMap already has the value, means we already                       
                                                 // have subarray with the sum - so stop                       
                                                 if                                     (hashMap.ContainsKey(cur_sum - sum))                       
                                                 {                       
                                                 start = hashMap[cur_sum - sum] + 1;                       
                                                 end = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 //if value is not present then add to hashmap                       
                                                 hashMap[cur_sum] = i;                       
           
                                                 }                       
                                                 // if end is -1 : means we have reached end without the sum                       
                                                 if                                     (end == -1)                       
                                                 {                       
                                                 Console.WriteLine(                                     "No subarray with given sum exists"                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 Console.WriteLine(                                     "Sum found between indexes "                                     + start +                                     " to "                                     + end);                       
                                                 }                       
           
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                                                 {                       
                                                 int                                     [] arr =                                     new                                     int                                     [] {10, 2, -2, -20, 10};                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     sum = -10;                       
                                                 subArraySum(arr, n, sum);                       
           
                                                 }                       
                         }                       
           
                         // This code is contributed by Shrikant13                       

Javascript

                         <script>                       
           
                         // Javascript program to print subarray with sum as given sum                       
           
                                                 function                                     subArraySum(arr, n, sum) {                       
                                                 //cur_sum to keep track of cumulative sum till that point                       
                                                 let cur_sum = 0;                       
                                                 let start = 0;                       
                                                 let end = -1;                       
                                                 let hashMap =                                     new                                     Map();                       
                                   
                                                 for                                     (let i = 0; i < n; i++) {                       
                                                 cur_sum = cur_sum + arr[i];                       
                                                 //check whether cur_sum - sum = 0, if 0 it means                       
                                                 //the sub array is starting from index 0- so stop                       
                                                 if                                     (cur_sum - sum == 0) {                       
                                                 start = 0;                       
                                                 end = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 //if hashMap already has the value, means we already                       
                                                 // have subarray with the sum - so stop                       
                                                 if                                     (hashMap.has(cur_sum - sum)) {                       
                                                 start = hashMap.get(cur_sum - sum) + 1;                       
                                                 end = i;                       
                                                 break                                     ;                       
                                                 }                       
                                                 //if value is not present then add to hashmap                       
                                                 hashMap.set(cur_sum, i);                       
                                   
                                                 }                       
                                                 // if end is -1 : means we have reached end without the sum                       
                                                 if                                     (end == -1) {                       
                                                 document.write(                                     "No subarray with given sum exists"                                     );                       
                                                 }                       
                                                 else                                     {                       
                                                 document.write(                                     "Sum found between indexes "                       
                                                 + start +                                     " to "                                     + end);                       
                                                 }                       
                                   
                                                 }                       
           
                         // Driver program                       
           
                                                 let arr = [10, 2, -2, -20, 10];                       
                                                 let n = arr.length;                       
                                                 let sum = -10;                       
                                                 subArraySum(arr, n, sum);                       
                                   
                         </script>                       

输出

Sum found between indexes 0 to 3

复杂性分析：

时间复杂性： O（N）。如果在数组的帮助下执行哈希，那么这就是时间复杂度。如果元素不能在数组中散列，也可以使用散列映射，如上面的代码所示。
辅助空间： O（n）。由于需要HashMap，这需要线性空间。

求给定和且在常数空间中允许负的子数组 本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章