Algorithm
Problem Name: 560. Subarray Sum Equals K
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2 Output: 2
Example 2:
Input: nums = [1,2,3], k = 3 Output: 2
Constraints:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct e_s {
int s;
int c;
struct e_s *next;
} e_t;
#define HF 1021
#define HC(S) (((S) % HF) + HF)
typedef struct {
e_t *e[HF * 2];
e_t buff[20000];
int n;
} ht_t;
e_t *lookup(ht_t *ht, int s) {
e_t *e = ht->e[HC(s)];
while (e && e->s != s) e = e->next;
return e;
}
void insert(ht_t *ht, int s) {
e_t *e = lookup(ht, s);
if (e) e->c ++;
else {
e = &ht->buff[ht->n ++];
e->s = s;
e->c = 1;
e->next = ht->e[HC(s)];
ht->e[HC(s)] = e;
}
}
int count(ht_t *ht, int s) {
e_t *e = lookup(ht, s);
if (e) return e->c;
return 0;
}
int subarraySum(int* nums, int numsSize, int k){
int i, s, r, n;
ht_t ht = { 0 };
n = 0;
s = 0;
insert(&ht, s);
for (i = 0; i < numsSize; i ++) {
s += nums[i];
n += count(&ht, s - k);
insert(&ht, s);
}
return n;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
unordered_map < int, int>m;
int sum = 0;
for(auto x: nums){
m[sum]++;
sum += x;
if(m.count(sum - k) > 0) count += m[sum - k];
}
return count;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0;
int count = 0;
Map < Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
start coding...Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def subarraySum(self, nums, k):
sums, res, sm = {}, 0, 0
for i in range(len(nums)):
sums[sm], sm = sm in sums and sums[sm] + 1 or 1, sm + nums[i]
if sm - k in sums: res += sums[sm - k]
return res
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0560_SubarraySumEqualsK
{
public int SubarraySum(int[] nums, int k)
{
var map = new Dictionary < int, int>();
map.Add(0, 1);
var sum = 0;
var count = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
if (map.ContainsKey(sum - k))
count += map[sum - k];
if (map.ContainsKey(sum))
map[sum] += 1;
else
map[sum] = 1;
}
return count;
}
}
}
Input
Output