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

问题A：给定N个石头的重量，找到一对重量差为D的石头。

函数F的输入为一个长度为N的数组weights和一个实数D，表示每个石头的重量和目标重量差。函数的输出是一个长度为2的数组，表示找到的一对石头的下标，如果不存在这样的石头对，则返回空数组。

问题B：首先，我们可以使用一个哈希表来存储每个石头的重量及其对应的下标，然后遍历每个石头，查找是否存在另一个石头的重量为当前石头的重量加上D或减去D。如果存在，则返回这两个石头的下标。

时间复杂度为O(N)，空间复杂度为O(N)，因为需要使用哈希表来存储石头的重量及其对应的下标。

同时，我们也可以实现O(N)的时间复杂度和O(1)的空间复杂度。我们可以先将石头按照重量从小到大排序，然后使用双指针法来查找一对石头的重量差为D。具体来说，我们可以使用两个指针i和j，分别指向已排序数组的开头和结尾。如果weights[j]-weights[i]>D，则向左移动指针i；如果weights[j]-weights[i]<D，则向右移动指针j；如果weights[j]-weights[i]=D，则返回这两个石头的下标。

时间复杂度为O(NlogN)，因为需要排序；空间复杂度为O(1)，因为只使用了常数个变量。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> findStonePair(vector<double>& weights, double D) {
    unordered_map<double, int> m;
    for (int i = 0; i < weights.size(); i++) {
        m[weights[i]] = i;
    }
    for (int i = 0; i < weights.size(); i++) {
        double target1 = weights[i] + D;
        double target2 = weights[i] - D;
        if (m.count(target1) && m[target1] != i) {
            return vector<int>{i, m[target1]};
        }
        if (m.count(target2) && m[target2] != i) {
            return vector<int>{i, m[target2]};
        }
    }
    return vector<int>{};
}

vector<int> findStonePair2(vector<double>& weights, double D) {
    sort(weights.begin(), weights.end());
    int i = 0, j = 1;
    while (j < weights.size()) {
        double diff = weights[j] - weights[i];
        if (diff == D) {
            return vector<int>{i, j};
        } else if (diff < D) {
            j++;
        } else {
            i++;
        }
    }
    return vector<int>{};
}

int main() {
    // Test case 1: normal case
    vector<double> weights1{1.2, 2.4, 3.6, 4.8, 6.0};
    double D1 = 2.4;
    vector<int> res1 = findStonePair(weights1, D1);
    vector<int> ans1{0, 1};
    sort(res1.begin(), res1.end());
    sort(ans1.begin(), ans1.end());
    assert(res1 == ans1);

    vector<int> res2 = findStonePair2(weights1, D1);
    sort(res2.begin(), res2.end());
    assert(res2 == ans1);

    // Test case 2: no pair exists
    vector<double> weights2{1.2, 2.4, 3.6, 4.8, 6.0};
    double D2 = 2.5;
    vector<int> res3 = findStonePair(weights2, D2);
    vector<int> ans2{};
    assert(res3 == ans2);

    vector<int> res4 = findStonePair2(weights2, D2);
    assert(res4 == ans2);

    // Test case 3: all weights are the same
    vector<double> weights3{1.0, 1.0, 1.0, 1.0};
    double D3 = 0.0;
    vector<int> res5 = findStonePair(weights3, D3);
    vector<int> ans3{0, 1};
    sort(res5.begin(), res5.end());
    sort(ans3.begin(), ans3.end());
    assert(res5 == ans3);

    vector<int> res6 = findStonePair2(weights3, D3);
    sort(res6.begin(), res6.end());
    assert(res6 == ans3);

    // Test case 4: only one stone
    vector<double> weights4{1.0};
    double D4 = 0.0;
    vector<int> res7 = findStonePair(weights4, D4);
    vector<int> ans4{};
    assert(res7 == ans4);

    vector<int> res8 = findStonePair2(weights4, D4);
    assert(res8 == ans4);

    cout << "All test cases passed.";
    return 0;
}

问题C：给定N个石头的重量，找到所有重量差为D的石头对，其中对(1,4)和对(4,1)被认为是同一对。

我们可以先按照重量从小到大排序，然后使用双指针法来查找一对石头的重量差为D。具体来说，我们可以使用两个指针i和j，分别指向已排序数组的开头和结尾。如果weights[j]-weights[i]>D，则向左移动指针i；如果weights[j]-weights[i]<D，则向右移动指针j；如果weights[j]-weights[i]=D，则将这两个石头的下标加入结果集合中，然后向右移动指针i，直到weights[j]-weights[i]>D为止。

时间复杂度为O(max(R, N))，其中R是结果对数，空间复杂度为O(1)。

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> findStonePairs(vector<double>& weights, double D) {
    sort(weights.begin(), weights.end());
    vector<vector<int>> res;
    int i = 0, j = 1;
    while (j < weights.size()) {
        double diff = weights[j] - weights[i];
        if (diff == D) {
            res.push_back(vector<int>{i, j});
            i++;
        } else if (diff < D) {
            j++;
        } else {
            i++;
        }
    }
    return res;
}

int main() {
    // Test case 1: normal case
    vector<double> weights1{1.2, 2.4, 3.6, 4.8, 6.0};
    double D1 = 2.4;
    vector<vector<int>> res1 = findStonePairs(weights1, D1);
    vector<vector<int>> ans1{{0, 1}, {1, 2}, {2, 3}, {3, 4}};
    sort(res1.begin(), res1.end());
    sort(ans1.begin(), ans1.end());
    assert(res1 == ans1);

    // Test case 2: no pair exists
    vector<double> weights2{1.2, 2.4, 3.6, 4.8, 6.0};
    double D2 = 2.5;
    vector<vector<int>> res2 = findStonePairs(weights2, D2);
    vector<vector<int>> ans2{};
    assert(res2 == ans2);

    // Test case 3: all weights are the same
    vector<double> weights3{1.0, 1.0, 1.0, 1.0};
    double D3 = 0.0;
    vector<vector<int>> res3 = findStonePairs(weights3, D3);
    vector<vector<int>> ans3{{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}};
    sort(res3.begin(), res3.end());
    sort(ans3.begin(), ans3.end());
    assert(res3 == ans3);

    // Test case 4: only one stone
    vector<double> weights4{1.0};
    double D4 = 0.0;
    vector<vector<int>> res4 = findStonePairs(weights4, D4);
    vector<vector<int>> ans4{};
    assert(res4 == ans4);

    cout << "All test cases passed.";
    return 0;
}