446. 等差数列划分 II - 子序列

    输入：nums = [2,4,6,8,10]
    输出：7
    解释：所有的等差子序列为：
    [2,4,6]
    [4,6,8]
    [6,8,10]
    [2,4,6,8]
    [4,6,8,10]
    [2,4,6,8,10]
    [2,6,10]
    
    
    plaintext
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-16/yZOhVURXSw5PoF3NLHJAMlEiGWsm.png)

    输入：nums = [7,7,7,7,7]
    输出：16
    解释：数组中的任意子序列都是等差子序列。
    
    
    plaintext

    #include <stdio.h>
    #include <stdlib.h>
    
    // 定义哈希表节点结构体
    typedef struct HashNode {
    long long diff;  // 公差
    int count;       // 以当前元素结尾且公差为 diff 的等差子序列数量
    struct HashNode *next;
    } HashNode;
    
    // 定义哈希表结构体
    typedef struct {
    HashNode **table;
    int size;
    } HashMap;
    
    // 创建新的哈希表节点
    HashNode* createHashNode(long long diff, int count) {
    HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    node->diff = diff;
    node->count = count;
    node->next = NULL;
    return node;
    }
    
    // 创建新的哈希表
    HashMap* createHashMap(int size) {
    HashMap *map = (HashMap*)malloc(sizeof(HashMap));
    map->table = (HashNode**)malloc(size * sizeof(HashNode*));
    map->size = size;
    for (int i = 0; i < size; i++) {
        map->table[i] = NULL;
    }
    return map;
    }
    
    // 哈希函数
    int hashFunction(long long diff, int size) {
    return (diff % size + size) % size;
    }
    
    // 向哈希表中插入或更新键值对
    void put(HashMap *map, long long diff, int count) {
    int index = hashFunction(diff, map->size);
    HashNode *node = map->table[index];
    while (node) {
        if (node->diff == diff) {
            node->count += count;
            return;
        }
        node = node->next;
    }
    node = createHashNode(diff, count);
    node->next = map->table[index];
    map->table[index] = node;
    }
    
    // 从哈希表中获取键对应的值
    int get(HashMap *map, long long diff) {
    int index = hashFunction(diff, map->size);
    HashNode *node = map->table[index];
    while (node) {
        if (node->diff == diff) {
            return node->count;
        }
        node = node->next;
    }
    return 0;
    }
    
    // 释放哈希表内存
    void freeHashMap(HashMap *map) {
    for (int i = 0; i < map->size; i++) {
        HashNode *node = map->table[i];
        while (node) {
            HashNode *temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(map->table);
    free(map);
    }
    
    // 等差数列划分 II - 子序列函数
    int numberOfArithmeticSlices(int* nums, int numsSize) {
    if (numsSize < 3) {
        return 0;
    }
    // 为每个元素创建一个哈希表
    HashMap **dp = (HashMap**)malloc(numsSize * sizeof(HashMap*));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = createHashMap(1000);
    }
    int result = 0;
    // 遍历数组
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            long long diff = (long long)nums[i] - nums[j];
            // 获取以 nums[j] 结尾且公差为 diff 的等差子序列数量
            int count = get(dp[j], diff);
            // 更新结果
            result += count;
            // 以 nums[i] 结尾且公差为 diff 的等差子序列数量增加
            put(dp[i], diff, count + 1);
        }
    }
    // 释放哈希表内存
    for (int i = 0; i < numsSize; i++) {
        freeHashMap(dp[i]);
    }
    free(dp);
    return result;
    }
    
    
    c
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-16/ksOruMf1o9dK0zEyPxnA3bc5ZFqg.png)

    int main() {
    int nums[] = {2, 4, 6, 8, 10};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = numberOfArithmeticSlices(nums, numsSize);
    printf("等差子序列的数目: %d\n", result);
    return 0;
    }
    
    
    c