LeetCode //C - 560. Subarray Sum Equals K

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
Explanation:

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

• $1<=nums.length<=2\ast 10^4$
• -1000 <= nums[i] <= 1000
• $-10^7<=k<=10^7$

From: LeetCode
Link: 560. Subarray Sum Equals K

---

Solution:

Ideas：

This code defines a simple hash table implementation for demonstration purposes, using linear probing for collision resolution. It’s crucial to note that, in practice, there are more efficient and sophisticated hash table implementations available in libraries or you could use data structures available in the standard libraries of high-level languages that abstract these details away. The hashInsert function updates the count of each cumulative sum encountered, and the hashFind function retrieves the count of a particular sum. This allows us to efficiently count the number of subarrays that sum to k.

Code:

// Definition for the hash table's element
typedef struct {
    int key;    // The cumulative sum
    int value;  // How many times this sum has occurred
} HashElement;

// Simple hash function
unsigned int hashFunction(int key, int size) {
    unsigned int hash = (unsigned int)key;
    return hash % size;
}

// Insert or update the hash table
void hashInsert(HashElement *table, int size, int key, int increment) {
    unsigned int hash = hashFunction(key, size);
    while (table[hash].value != 0 && table[hash].key != key) {
        hash = (hash + 1) % size; // Linear probing
    }
    if (table[hash].value == 0) { // New insertion
        table[hash].key = key;
    }
    table[hash].value += increment;
}

// Find a value by key in the hash table
int hashFind(HashElement *table, int size, int key) {
    unsigned int hash = hashFunction(key, size);
    while (table[hash].value != 0) {
        if (table[hash].key == key) {
            return table[hash].value;
        }
        hash = (hash + 1) % size; // Linear probing
    }
    return 0; // Not found
}

// Function to calculate the number of subarrays that sum up to k
int subarraySum(int* nums, int numsSize, int k) {
    int count = 0, sum = 0;
    int tableSize = numsSize * 2; // To reduce collision probability
    HashElement *table = (HashElement *)calloc(tableSize, sizeof(HashElement));

    // Handle the case when the running sum equals k itself
    hashInsert(table, tableSize, 0, 1);

    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        count += hashFind(table, tableSize, sum - k);
        hashInsert(table, tableSize, sum, 1);
    }

    free(table); // Don't forget to free the allocated memory!
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54