代码不适用于查找产品对的负面测试用例[已关闭]

Question

产品对-问题链接

最初我没有添加abs东西，但是在我添加之后，代码能够处理一些负面测试用例，但不是全部

我知道为什么即使添加了abs部分后仍然可能显示错误，但我无法准确指出它，更不用说知道如何纠正问题了，所以我需要帮助。

ps：我是第一次在 stackoverflow 上发帖，所以如果格式或其他东西不合适，我真的很抱歉

class Solution{   
public:
    bool isProduct(int arr[], int n, long long x) {
       
        for (int i = 0; i < n; i++) {
        arr[i] = abs(arr[i]);
        }
        x=abs(x);
        sort(arr, arr + n);
        int start = 0, end = n - 1;

        while (start < end) {
            if (arr[start] * arr[end] == x) {
                return true;
            } else if (arr[start] * arr[end] < x) {
                start++;
            } else {
                end--;
            }
        }
        return false;
    }
};

Answer 1

给定一个大小为 N 的不同元素的数组 arr[] 和一个数字 X，查找 arr[] 中是否存在一对，其乘积等于 X。

您正在搜索数组中的一对项目是否有 X 作为乘积。这表明您可能有一个嵌套循环，如下所示：

bool isProduct(int arr[], int n, long long x) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] * arr[j] == x) return true; //found a pair
        }
    }
    return false;
}

在上面，我们循环所有元素，对于每个元素，我们循环后面的元素，并检查每个这样的对是否符合条件（乘积等于

x

）。如果存在匹配，算法将立即停止并返回 true。如果没有任何对匹配，该函数将返回 false。您还可以通过以下方式优化上述方法：

bool isProduct(int arr[], int n, long long x) {
    int item;
    for (int i = 0; i < n; i++) {
        if (arr[i] % x == 0) {
            item = x / arr[i];
            for (int j = i + 1; j < n; j++) {
                if (arr[j] == item) return true; //found a pair
            }
        }
    }
    return false;
}

上面使用了一些数学知识，使得算法更快。首先，如果

arr[i]

不是

x

的约数，那么我们就不需要嵌套循环，因此我们会删除很多不可能有正确对的情况。

其次，我们计算除法并将结果存储到局部变量中，

item

，因此稍后在循环中我们会根据它检查值，而不是在每个步骤中计算乘积。

你的算法有多个错误：

• 您将值更改为其绝对值，因此假设 x 是 -26，并且元素中有 -2 和 -13。那么你的算法将推断 -26 = -2 * -13，这是错误的
• 您可以通过比较 < and > 从下限和上限接近中位数，但如果项目可能为负数，则这是不稳定的