# 算法题：总和等于k的子数组数

2021年4月17日18:34:36 发表评论 778 次浏览

## 本文概述

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

Input : arr[] = {9, 4, 20, 3, 10, 5}, k = 33
Output : 2
Subarrays : arr[0...2], arr[2...4] have sum
exactly 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

``````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);
}
}``````

``3``

## 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))
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``````

``3``