和正好等于k的子阵列数-yiteyi-C++库

给定一个未排序的整数数组，求和正好等于给定数k的子数组数。

null

例如：

Input : arr[] = {10, 2, -2, -20, 10},         k = -10Output : 3Subarrays: arr[0...3], arr[1...4], arr[3..4]have sum exactly equal to -10.Input : arr[] = {9, 4, 20, 3, 10, 5},            k = 33Output : 2Subarrays : arr[0...2], arr[2...4] have sumexactly equal to 33.

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

天真的解决方案—— 一个简单的解决方案是遍历所有子阵列并计算它们的和。如果总和等于所需总和，则增加子阵列的计数。打印子阵列的最终计数。以下是天真的实现——

C++

                         // C++ program for                       
                         // the above approach                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {10, 2, -2, -20, 10};                       
                                                 int                                     k = -10;                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     res = 0;                       
           
                                                 // Calculate all subarrays                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     j = i; j < n; j++)                       
                                                 {                       
                                                 // Calculate required sum                       
                                                 sum += arr[j];                       
           
                                                 // Check if sum is equal to                       
                                                 // required sum                       
                                                 if                                     (sum == k)                       
                                                 res++;                       
                                                 }                       
                                                 }                       
                                                 cout << (res) << endl;                       
                         }                       
           
                         // This code is contributed by Chitranayal                       

JAVA

                         // Java program for                       
                         // the above approach                       
                         import                                     java.util.*;                       
                         class                                     Solution {                       
                                   
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     10                                     ,                                     2                                     , -                                     2                                     , -                                     20                                     ,                                     10                                     };                       
                                                 int                                     k = -                                     10                                     ;                       
                                                 int                                     n = arr.length;                       
                                                 int                                     res =                                     0                                     ;                       
                                   
                                                 // calculate all subarrays                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                   
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     j = i; j < n; j++) {                       
                                   
                                                 // calculate required sum                       
                                                 sum += arr[j];                       
                                   
                                                 // check if sum is equal to                       
                                                 // required sum                       
                                                 if                                     (sum == k)                       
                                                 res++;                       
                                                 }                       
                                                 }                       
                                                 System.out.println(res);                       
                                                 }                       
                         }                       

Python3

                         # Python3 program for                       
                         # the above approach                       
                         arr                                     =                                     [                                     10                                     ,                                     2                                     ,                                     -                                     2                                     ,                                     -                                     20                                     ,                                     10                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         k                                     =                                     -                                     10                       
                         res                                     =                                     0                       
           
                         # Calculate all subarrays                       
                         for                                     i                                     in                                     range                                     (n):                       
                                                 summ                                     =                                     0                       
                                                 for                                     j                                     in                                     range                                     (i, n):                       
                                   
                                                 # Calculate required sum                       
                                                 summ                                     +                                     =                                     arr[j]                       
           
                                                 # Check if sum is equal to                       
                                                 # required sum                       
                                                 if                                     summ                                     =                                     =                                     k:                       
                                                 res                                     +                                     =                                     1                       
           
                         print                                     (res)                       
           
                         # This code is contributed by kavan155gondalia                       

C#

                         // C# program for                       
                         // the above approach                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         class                                     GFG {                       
                                   
                                                 static                                     void                                     Main() {                       
                                                 int                                     [] arr = {10, 2, -2, -20, 10};                       
                                                 int                                     k = -10;                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     res = 0;                       
                                   
                                                 // Calculate all subarrays                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     j = i; j < n; j++)                       
                                                 {                       
                                   
                                                 // Calculate required sum                       
                                                 sum += arr[j];                       
                                   
                                                 // Check if sum is equal to                       
                                                 // required sum                       
                                                 if                                     (sum == k)                       
                                                 res++;                       
                                                 }                       
                                                 }                       
                                                 Console.WriteLine(res);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by divyesh072019                       

Javascript

                         <script>                       
                                   
                         // Javascript program for                       
                         // the above approach                       
                         let arr = [ 10, 2, -2, -20, 10 ];                       
                         let k = -10;                       
                         let n = arr.length;                       
                         let res = 0;                       
           
                         // Calculate all subarrays                       
                         for                                     (let i = 0; i < n; i++)                       
                         {                       
                                                 let sum = 0;                       
                                                 for                                     (let j = i; j < n; j++)                       
                                                 {                       
                                   
                                                 // Calculate required sum                       
                                                 sum += arr[j];                       
                                   
                                                 // Check if sum is equal to                       
                                                 // required sum                       
                                                 if                                     (sum == k)                       
                                                 res++;                       
                                                 }                       
                         }                       
                         document.write(res);                       
           
                         // This code is contributed by suresh07                       
                                   
                         </script>                       

输出：

有效的解决方案—— 一个有效的解决方案是在遍历数组时，将迄今为止的总和存储为currsum。此外，在映射中保持currsum不同值的计数。如果currsum的值在任何情况下都等于所需的和，则子阵列的计数将增加1。currsum的值超过了currsum–sum的期望值。如果从currsum中删除该值，则可以获得所需的和。从图中找到以前发现的sum等于currsum的子阵列数。从当前子阵列中排除所有这些子阵列，将生成具有所需和的新子阵列。所以增加这样子阵列的数量。请注意，当currsum等于所需的和时，还要检查之前的和等于0的子阵列数。将这些子阵列从当前子阵列中排除会产生具有所需和的新子阵列。在这种情况下，按总和为0的子阵列数增加计数。

C++

                         // C++ program to find number of subarrays                       
                         // with sum exactly equal to k.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find number of subarrays                       
                         // with sum exactly equal to k.                       
                         int                                     findSubarraySum(                                     int                                     arr[],                                     int                                     n,                                     int                                     sum)                       
                         {                       
                                                 // STL map to store number of subarrays                       
                                                 // starting from index zero having                       
                                                 // particular value of sum.                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > prevSum;                       
           
                                                 int                                     res = 0;                       
           
                                                 // Sum of elements so far.                       
                                                 int                                     currsum = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // Add current element to sum so far.                       
                                                 currsum += arr[i];                       
           
                                                 // If currsum is equal to desired sum,                       
                                                 // then a new subarray is found. So                       
                                                 // increase count of subarrays.                       
                                                 if                                     (currsum == sum)                       
                                                 res++;                       
           
                                                 // currsum exceeds given sum by currsum                       
                                                 //  - sum. Find number of subarrays having                       
                                                 // this sum and exclude those subarrays                       
                                                 // from currsum by increasing count by                       
                                                 // same amount.                       
                                                 if                                     (prevSum.find(currsum - sum) != prevSum.end())                       
                                                 res += (prevSum[currsum - sum]);                       
           
                                                 // Add currsum value to count of                       
                                                 // different values of sum.                       
                                                 prevSum[currsum]++;                       
                                                 }                       
           
                                                 return                                     res;                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 10, 2, -2, -20, 10 };                       
                                                 int                                     sum = -10;                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << findSubarraySum(arr, n, sum);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find number of subarrays                       
                         // with sum exactly equal to k.                       
                         import                                     java.util.HashMap;                       
                         import                                     java.util.Map;                       
           
                         public                                     class                                     GfG {                       
           
                                                 // Function to find number of subarrays                       
                                                 // with sum exactly equal to k.                       
                                                 static                                     int                                     findSubarraySum(                                     int                                     arr[],                                     int                                     n,                                     int                                     sum)                       
                                                 {                       
                                                 // HashMap to store number of subarrays                       
                                                 // starting from index zero having                       
                                                 // particular value of sum.                       
                                                 HashMap<Integer, Integer> prevSum =                                     new                                     HashMap<>();                       
           
                                                 int                                     res =                                     0                                     ;                       
           
                                                 // Sum of elements so far.                       
                                                 int                                     currsum =                                     0                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
           
                                                 // Add current element to sum so far.                       
                                                 currsum += arr[i];                       
           
                                                 // If currsum is equal to desired sum,                       
                                                 // then a new subarray is found. So                       
                                                 // increase count of subarrays.                       
                                                 if                                     (currsum == sum)                       
                                                 res++;                       
           
                                                 // currsum exceeds given sum by currsum                       
                                                 //  - sum. Find number of subarrays having                       
                                                 // this sum and exclude those subarrays                       
                                                 // from currsum by increasing count by                       
                                                 // same amount.                       
                                                 if                                     (prevSum.containsKey(currsum - sum))                       
                                                 res += prevSum.get(currsum - sum);                       
           
                                                 // Add currsum value to count of                       
                                                 // different values of sum.                       
                                                 Integer count = prevSum.get(currsum);                       
                                                 if                                     (count ==                                     null                                     )                       
                                                 prevSum.put(currsum,                                     1                                     );                       
                                                 else                       
                                                 prevSum.put(currsum, count +                                     1                                     );                       
                                                 }                       
           
                                                 return                                     res;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 int                                     arr[] = {                                     10                                     ,                                     2                                     , -                                     2                                     , -                                     20                                     ,                                     10                                     };                       
                                                 int                                     sum = -                                     10                                     ;                       
                                                 int                                     n = arr.length;                       
                                                 System.out.println(findSubarraySum(arr, n, sum));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rituraj Jain                       

Python3

                         # Python3 program to find the number of                       
                         # subarrays with sum exactly equal to k.                       
                         from                                     collections                                     import                                     defaultdict                       
           
                         # Function to find number of subarrays                       
                         # with sum exactly equal to k.                       
                         def                                     findSubarraySum(arr, n,                                     Sum                                     ):                       
                                   
                                                 # Dictionary to store number of subarrays                       
                                                 # starting from index zero having                       
                                                 # particular value of sum.                       
                                                 prevSum                                     =                                     defaultdict(                                     lambda                                     :                                     0                                     )                       
                                   
                                                 res                                     =                                     0                       
                                   
                                                 # Sum of elements so far.                       
                                                 currsum                                     =                                     0                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                   
                                                 # Add current element to sum so far.                       
                                                 currsum                                     +                                     =                                     arr[i]                       
                                   
                                                 # If currsum is equal to desired sum,                       
                                                 # then a new subarray is found. So                       
                                                 # increase count of subarrays.                       
                                                 if                                     currsum                                     =                                     =                                     Sum                                     :                       
                                                 res                                     +                                     =                                     1                       
                                   
                                                 # currsum exceeds given sum by currsum  - sum.                       
                                                 # Find number of subarrays having                       
                                                 # this sum and exclude those subarrays                       
                                                 # from currsum by increasing count by                       
                                                 # same amount.                       
                                                 if                                     (currsum                                     -                                     Sum                                     )                                     in                                     prevSum:                       
                                                 res                                     +                                     =                                     prevSum[currsum                                     -                                     Sum                                     ]                       
                                   
                                   
                                                 # Add currsum value to count of                       
                                                 # different values of sum.                       
                                                 prevSum[currsum]                                     +                                     =                                     1                       
                                   
                                                 return                                     res                       
                                   
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 arr                                     =                                     [                                     10                                     ,                                     2                                     ,                                     -                                     2                                     ,                                     -                                     20                                     ,                                     10                                     ]                       
                                                 Sum                                     =                                     -                                     10                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 print                                     (findSubarraySum(arr, n,                                     Sum                                     ))                       
                                   
                         # This code is contributed by Rituraj Jain                       

C#

                         // C# program to find number of subarrays                       
                         // with sum exactly equal to k.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG {                       
                                                 // Function to find number of subarrays                       
                                                 // with sum exactly equal to k.                       
                                                 public                                     static                                     int                                     findSubarraySum(                                     int                                     [] arr,                       
                                                 int                                     n,                                     int                                     sum)                       
                                                 {                       
           
                                                 // HashMap to store number of subarrays                       
                                                 // starting from index zero having                       
                                                 // particular value of sum.                       
                                                 Dictionary<                                     int                                     ,                                     int                                     > prevSum =                                     new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
           
                                                 int                                     res = 0;                       
           
                                                 // Sum of elements so far                       
                                                 int                                     currsum = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // Add current element to sum so far.                       
                                                 currsum += arr[i];                       
           
                                                 // If currsum is equal to desired sum,                       
                                                 // then a new subarray is found. So                       
                                                 // increase count of subarrays.                       
                                                 if                                     (currsum == sum)                       
                                                 res++;                       
           
                                                 // currsum exceeds given sum by currsum                       
                                                 // - sum. Find number of subarrays having                       
                                                 // this sum and exclude those subarrays                       
                                                 // from currsum by increasing count by                       
                                                 // same amount.                       
                                                 if                                     (prevSum.ContainsKey(currsum - sum))                       
                                                 res += prevSum[currsum - sum];                       
           
                                                 // Add currsum value to count of                       
                                                 // different values of sum.                       
                                                 if                                     (!prevSum.ContainsKey(currsum))                       
                                                 prevSum.Add(currsum, 1);                       
                                                 else                                     {                       
                                                 int                                     count = prevSum[currsum];                       
                                                 prevSum[currsum] = count + 1;                       
                                                 }                       
                                                 }                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 10, 2, -2, -20, 10 };                       
                                                 int                                     sum = -10;                       
                                                 int                                     n = arr.Length;                       
                                                 Console.Write(findSubarraySum(arr, n, sum));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // sanjeev2552                       

Javascript

                         <script>                       
                         // Javascript program to find number of subarrays                       
                         // with sum exactly equal to k.                       
                                   
                                                 // Function to find number of subarrays                       
                                                 // with sum exactly equal to k.                       
                                                 function                                     findSubarraySum(arr,n,sum)                       
                                                 {                       
                                   
                                                 // HashMap to store number of subarrays                       
                                                 // starting from index zero having                       
                                                 // particular value of sum.                       
                                                 let prevSum =                                     new                                     Map();                       
                                                 let res = 0;                       
                                   
                                                 // Sum of elements so far.                       
                                                 let currsum = 0;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // Add current element to sum so far.                       
                                                 currsum += arr[i];                       
                                   
                                                 // If currsum is equal to desired sum,                       
                                                 // then a new subarray is found. So                       
                                                 // increase count of subarrays.                       
                                                 if                                     (currsum == sum)                       
                                                 res++;                       
                                   
                                                 // currsum exceeds given sum by currsum                       
                                                 //  - sum. Find number of subarrays having                       
                                                 // this sum and exclude those subarrays                       
                                                 // from currsum by increasing count by                       
                                                 // same amount.                       
                                                 if                                     (prevSum.has(currsum - sum))                       
                                                 res += prevSum.get(currsum - sum);                       
                                   
                                                 // Add currsum value to count of                       
                                                 // different values of sum.                       
                                                 let count = prevSum.get(currsum);                       
                                                 if                                     (count ==                                     null                                     )                       
                                                 prevSum.set(currsum, 1);                       
                                                 else                       
                                                 prevSum.set(currsum, count + 1);                       
                                                 }                       
                                                 return                                     res;                       
                                                 }                       
                                   
                                                 let arr = [10, 2, -2, -20, 10];                       
                                                 let sum = -10;                       
                                                 let n = arr.length;                       
                                                 document.write(findSubarraySum(arr, n, sum));                       
                                   
                                                 // This code is contributed by avanitrachhadiya2155.                       
                         </script>                       

输出：

时间复杂性： O（n） 辅助空间： O（n）

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

THE END

技术文章