c++实现：问题2：查找石头对 有N个编号为[0,N-1]的石头，我们知道每个石头的重量。我们想要找到一对石头，即2个石头，它们的重量差为D。 问题A 正式描述问题以清楚地定义问题，没有歧义。例如：编写一个函数F，它的输入是...函数的输出是...这个问题可能比你想象的要难，请仔细思考。 问题B 1.编写你在问题A中描述的函数。 2.你的算法的空间复杂度是什么？时间复杂度是什么？ 3.你能够实现O(N)的时间复杂度和空间复杂度吗？如果可以，请实现它。 4.编写一个测试程序来测试你的函数。 a.请列出你想要测试的所有边界情况。 b.如何验证函数能够正确处理这些边界情况？你能以更系统化的方式进行吗？ 问题C（可选） 与原问题B相同，但这次我们想要找到所有重量差为D的石头对。请注意，石头对(1,4)和(4,1)被视为同一对，因此只需要返回一对。你的算法的时间复杂度应为O(max(R,N))，其中R为结果对数，N为石头数。

问题A：
编写一个函数findStonePair，它的输入是一个整数数组stones和一个整数D，表示石头的重量和重量差，函数的输出是一个长度为2的整数数组，表示重量差为D的石头对的编号。如果没有重量差为D的石头对，则返回[-1,-1]。

问题B：
1. 实现findStonePair函数：

#include <unordered_map>
#include <vector>

std::vector<int> findStonePair(const std::vector<int>& stones, int D) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < stones.size(); i++) {
        int target = stones[i] - D;
        if (map.count(target)) {
            return std::vector<int>{map[target], i};
        }
        map[stones[i]] = i;
    }
    return std::vector<int>{-1, -1};
}

2. 算法的空间复杂度为O(N)，时间复杂度为O(N)，其中N为石头数量。

3. 可以实现O(N)的时间复杂度和空间复杂度。可以通过排序石头数组，然后使用双指针来查找重量差为D的石头对。具体实现如下：

#include <algorithm>
#include <vector>

std::vector<int> findStonePair(const std::vector<int>& stones, int D) {
    std::vector<int> sorted_stones = stones;
    std::sort(sorted_stones.begin(), sorted_stones.end());
    int left = 0, right = 1;
    while (right < sorted_stones.size()) {
        int diff = sorted_stones[right] - sorted_stones[left];
        if (diff == D) {
            // 找到了重量差为D的石头对
            int left_index = std::find(stones.begin(), stones.end(), sorted_stones[left]) - stones.begin();
            int right_index = std::find(stones.begin(), stones.end(), sorted_stones[right]) - stones.begin();
            return std::vector<int>{left_index, right_index};
        } else if (diff < D) {
            right++;
        } else {
            left++;
            if (left == right) {
                right++;
            }
        }
    }
    return std::vector<int>{-1, -1};
}

4. 编写一个测试程序：

#include <iostream>

void testFindStonePair() {
    std::vector<int> stones{3, 1, 4, 6, 5};
    int D = 2;
    std::vector<int> expected{0, 2};
    std::vector<int> result = findStonePair(stones, D);
    if (result == expected) {
        std::cout << "Test case 1 passed\n";
    } else {
        std::cout << "Test case 1 failed\n";
    }

    stones = {3, 1, 4, 6, 5};
    D = 3;
    expected = {0, 3};
    result = findStonePair(stones, D);
    if (result == expected) {
        std::cout << "Test case 2 passed\n";
    } else {
        std::cout << "Test case 2 failed\n";
    }

    stones = {3, 1, 4, 6, 5};
    D = 4;
    expected = {-1, -1};
    result = findStonePair(stones, D);
    if (result == expected) {
        std::cout << "Test case 3 passed\n";
    } else {
        std::cout << "Test case 3 failed\n";
    }

    stones = {};
    D = 2;
    expected = {-1, -1};
    result = findStonePair(stones, D);
    if (result == expected) {
        std::cout << "Test case 4 passed\n";
    } else {
        std::cout << "Test case 4 failed\n";
    }

    stones = {1};
    D = 2;
    expected = {-1, -1};
    result = findStonePair(stones, D);
    if (result == expected) {
        std::cout << "Test case 5 passed\n";
    } else {
        std::cout << "Test case 5 failed\n";
    }
}

int main() {
    testFindStonePair();
    return 0;
}

a. 边界情况包括：

- 石头数组为空。
- 石头数组只有一个元素。
- 石头数组中不存在重量差为D的石头对。
- 石头数组中存在多个重量差为D的石头对。

b. 可以通过手动计算每个边界情况的预期结果，并将其与实际结果进行比较来验证函数的正确性。可以使用更系统化的方式，如使用单元测试框架编写多个测试用例，并自动验证函数的正确性。