3115.质数的最大距离

#medium
给你一个整数数组 nums。

返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。
思路
从头遍历找到第一个质数在从尾便利找到最后一个质数相减即可。

bool isPrime(int n) {
    if (n <= 3) {
        return n > 1;
    }
    // 只需判断一个数能否被小于sqrt(n)的奇数整除
    int sqrt = (int)pow(n, 0.5);
    for (int i = 2; i <= sqrt; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int maximumPrimeDifference(int* nums, int numsSize) {
    int first = -1;
    for (int i = 0; i < numsSize; i++) {
        if (isPrime(nums[i])) {
            first = i;
            break;
        }
    }
    for (int i = numsSize - 1; i >= 0; i--) {
        if (isPrime(nums[i]))
            return i - first;
    }
    return 0;
}

官方题解由于范围在 100 内可以用打表的方式来判断质数。

typedef struct {
    int key;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);
    }
}

int maximumPrimeDifference(int* nums, int numsSize) {
    int primes[] = {
        2, 3, 5, 7, 11,
        13, 17, 19, 23, 29,
        31, 37, 41, 43, 47,
        53, 59, 61, 67, 71,
        73, 79, 83, 89, 97
    };
    int primesSize = sizeof(primes) / sizeof(int);
    HashItem *set = NULL;
    for (int i = 0; i < primesSize; i++) {
        hashAddItem(&set, primes[i]);
    }

    int first = -1, ans = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (hashFindItem(&set, nums[i])) {
            if (first != -1) {
                ans = fmax(ans, i - first);
            } else {
                first = i;
            }
        }
    }
    hashFree(&set);
    return ans;
}