给定差值的组合

一、题目

给定差值的组合
给定一个数组，每个元素的值是唯一的，找出其中两个元素相减等于给定差值 diff 的所有不同组合的个数。
组合是无序的：如：（1, 4)和(4, 1)表示的是同一个组合。
输入
第一个参数为 diff，-50000 <= diff <= 50000
第二个参数为数组 numbers，2 <= numbers.length <= 102400, -20 <= numbers[i] <= 102400
输出
1个整数，表示满足要求的不同组合的个数

样例1
复制输入：
3
[1, 3, 2, 5, 4]
复制输出：
2
解释：
差值 diff 为 3，其中 4 - 1 = 3，5 - 2 = 3，共 2 个组合满足条件，因此输出 2

样例2
复制输入：
-1
[1, 2, 3]
复制输出：
2
解释：
其中 1 - 2 = -1，2 - 3 = -1，共 2 个组合满足条件，因此输出 2。

代码框架

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "securec.h"
#include "solution.c"

// 以下为考题输入输出框架，此部分代码不建议改动；提交代码时请勿包含下面代码
static int *ExpandListInt(int *ptr, size_t oldLen, size_t newLen)
{
    int *newPtr = (int *)malloc(newLen * sizeof(*ptr));
    if (newPtr) {
        for (size_t i = 0; i < oldLen; ++i) {
            newPtr[i] = ptr[i];
        }
    }
    if (ptr) { free(ptr); }
    return newPtr;
}

static void SkipWs(void)
{
    char c = (char)getchar();
    while (c == ' ' || c == '\r' || c == '\n') {
        c = (char)getchar();
    }
    (void)ungetc(c, stdin);
}

static void FreeListInt(int *value)
{
    if (!value) { return; }
    free(value);
}

static bool ReadListInt(int **value, size_t *size)
{
    SkipWs();
    char c = (char)getchar();
    if (c != '[') { return false; }

    SkipWs();
    c = (char)getchar();
    if (c == ']') {
        *value = NULL;
        *size = 0;
        return true;
    }
    (void)ungetc(c, stdin);

    size_t cap = 32;
    for (size_t pos = 0;; ++pos) {
        if (pos == 0 || pos >= cap) {
            cap *= 2;
            *value = ExpandListInt(*value, pos, cap);
            if (*value == NULL) { break; }
        }
        if (scanf_s("%d", &(*value)[pos]) != 1) { break; }

        SkipWs();
        int in = getchar();
        if (in == EOF) { break; }
        if ((char)in == ']') {
            *size = pos + 1;
            return true;
        }
        if ((char)in != ',') { break; }
    }

    FreeListInt(*value);
    *value = NULL;
    return false;
}

int main(void)
{
    int diff = 0;
    int *numbers = NULL;
    size_t numbersSize = 0;
    int returnValue = 0;
    bool isOk = false;

    do {
        if (scanf_s("%d", &diff) != 1) { break; }
        if (!ReadListInt(&numbers, &numbersSize)) { break; }
        isOk = true;
        returnValue = GetDiffCnt(diff, numbers, numbersSize);
        printf("%d", returnValue);
    } while (false);

    if (!isOk) { printf("Error: Input format incorrect!"); }
    FreeListInt(numbers);
    numbers = NULL;

    return 0;
}

二、解题

方法一

两层for循环

static int GetDiffCnt2(int diff, const int* numbers, size_t numbersSize)
{
    int count = 0;
    for (int i = 0; i < numbersSize; i++) {
        for (int j = i + 1; j < numbersSize; j++) {
            if (numbers[i] - numbers[j] == diff || numbers[j] - numbers[i] == diff) {
                count++;
            }
        }
    }
    return count;
}

方法二

快慢指针

static int compareUpper(const void* a, const void* b)
{
    return *(int*) a - *(int*) b;
}

static int compareLower(const void* a, const void* b)
{
    return *(int*) b - *(int*) a;
}

static int GetDiffCnt(int diff, const int* numbers, size_t numbersSize)
{
    int count = 0;
    bool upperFlag = false;
    if (diff >= 0) {
        qsort(numbers, numbersSize, sizeof(int), compareUpper);
        upperFlag = true;
    } else {
        qsort(numbers, numbersSize, sizeof(int), compareLower);
    }

    int num[510];
    memcpy_s(num, 510 * sizeof(int), numbers, 510 * sizeof(int));

    int slow = 0;
    int fast = slow + 1;
    while (slow < fast && fast < numbersSize) {
        if (numbers[fast] - numbers[slow] == diff) {
            count++;
            slow++;
            fast++;
        } else if (numbers[fast] - numbers[slow] > diff) {
            if (upperFlag) {
                slow++;
            } else {
                fast++;
            }
        } else if (numbers[fast] - numbers[slow] < diff) {
            if (upperFlag) {
                fast++;
            } else {
                slow++;
            }
        }
    }

    return count;
}

上述两个方法都可以通过下述样例