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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
int val;
struct node *next;
};
struct table {
int size;
struct node **list;
};
struct table *createTable(int size) {
struct table *t = (struct table *)malloc(sizeof(struct table));
t->size = size;
t->list = (struct node **)malloc(sizeof(struct node *) * size);
for (int i = 0; i < size; i++)
t->list[i] = NULL;
return t;
}
int hashCode(struct table *t, int key) {
if (key < 0)
return -(key % t->size);
return key % t->size;
}
void insert(struct table *t, int key, int val) {
int pos = hashCode(t, key);
struct node *list = t->list[pos];
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->key = key;
newNode->val = val;
newNode->next = list;
t->list[pos] = newNode;
}
int lut(struct table *t, int key) {
int pos = hashCode(t, key);
struct node *list = t->list[pos];
struct node *tmp = list;
while (tmp) {
if (tmp->key == key)
return tmp->val;
tmp = tmp->next;
}
return INT_MAX;
}
bool checkSubarraySum(int *nums, int numsSize, int k) {
struct table *t = createTable(10);
int sum = 0;
insert(t, 0, -1);
for (int i = 0; i < numsSize; i++) {
sum += nums[i];
if (k)
sum %= k;
if (lut(t, sum) != INT_MAX) {
if (i - lut(t, sum) > 1)
return true;
} else
insert(t, sum, i);
}
return false;
}
int main() {
int nums1[] = {23, 2, 4, 6, 7}, nums2[] = {23, 2, 6, 4, 7};
printf("%d\n", checkSubarraySum(nums1, 5, 6)); // expect: 1
printf("%d\n", checkSubarraySum(nums2, 5, 6)); // expect: 1
printf("%d\n", checkSubarraySum(nums2, 5, 13)); // expect: 0
}
|