题解 | #未排序数组中累加和为给定值的最长子数组长度#

#include <stdio.h>
#include <stdlib.h>
typedef struct hashtable {
    int val;
    int key;
    struct hashtable* next;
} hashtable;
hashtable* hashfind(hashtable** head, int key) {
    int index = (key % 33119 + 33119) % 33119;
    hashtable* cur = head[index];
    if (cur == NULL)
        return NULL;
    while (cur) {
        if (cur->key == key)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
void hashadd(hashtable** head, int key, int val) {
    int index = (key % 33119 + 33119) % 33119;
    if (head[index] == NULL) {
        hashtable* node = malloc(sizeof(hashtable));
        node->key = key;
        node->val = val;
        node->next = NULL;
        head[index] = node;
    } else {
        hashtable* cur = head[index];
        hashtable* prev = NULL;
        while (cur) {
            if (cur->key == key) {
                return;
            }
            prev = cur;
            cur = cur->next;
        }
        // 如果没找到，添加到链表末尾
        hashtable* node = malloc(sizeof(hashtable));
        node->key = key;
        node->val = val;
        node->next = NULL;
        prev->next = node;
    }
}
int main() {
    hashtable** head = malloc(1000000 * sizeof(hashtable*));
    for (int i = 0; i < 1000000; i++)
        head[i] = NULL;
    int nums[100001];
    int n, target;
    scanf("%d %d", &n, &target);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    int sum = 0;
    hashadd(head, 0, -1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        sum += nums[i];
        hashtable* cur = hashfind(head, sum-target);
        if (cur != NULL) {
            ans = ans > i - cur->val ? ans : i - cur->val;
        }
        cur = hashfind(head, sum);
        if (cur == NULL) {
            hashadd(head, sum, i);
        }
    }
    for (int i = 0; i < 1000000; i++) {
        hashtable* cur = head[i];
        while (cur) {
            hashtable* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    free(head);
    printf("%d",ans);
}