aboutsummaryrefslogtreecommitdiff
path: root/continuous_subarr_sum.c
blob: 06879a39785bcfac0baee6689ef40355c23387ff (plain)
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
}