双指针-遍历方向导致的问题

Question

这是一个求数组元素目标和的算法题，复杂度要求O(n)，我用了双指针来做，下面这个是AC的代码。

#include<bits/stdc++.h>
using namespace std;
const int N = 100003;
int a[N], b[N];

int main() {
    int n, m, x;
    cin >> n >> m >> x;

    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    for (int i = 0, j = m-1; i < n; i++) {
        while (j >=0 && a[i] + b[j] > x)
            j--;
        //b从大到小遍历
        if (j >= 0 && a[i] + b[j] == x) {
            cout << i << " " << j;
            return 0;
        }
    }

下面是我将b从小到大遍历的代码，只是改动了遍历方向，且测试之后发现不会溢出，可以取到尾值，但为什么不AC呢，请大家帮忙答疑。

#include<bits/stdc++.h>
using namespace std;
const int N = 100003;
int a[N], b[N];

int main() {
    int n, m, x;
    cin >> n >> m >> x;

    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    //b从小到大遍历
    for (int i = 0, j = 0; i < n; i++) {
        while (j < m && a[i] + b[j] < x)
            j++;

        if (j < m && a[i] + b[j] == x) {
            cout << i << " " << j;
            return 0;
        }
        j--;
    }
}

Answer 1

【以下回答由 GPT 生成】

在代码的第二段中，将b数组的遍历顺序改为从小到大时出现问题的原因是在while循环的条件中使用了错误的判断，应该是a[i] + b[j] > x，而不是a[i] + b[j] < x。这个错误导致了循环的终止条件不正确，从而导致结果不准确。

以下是正确的代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 100003;
int a[N], b[N];

int main() {
    int n, m, x;
    cin >> n >> m >> x;

    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    // b从小到大遍历
    for (int i = 0, j = 0; i < n; i++) {
        while (j < m && a[i] + b[j] > x)
            j++;

        if (j < m && a[i] + b[j] == x) {
            cout << i << " " << j;
            return 0;
        }
        j--;
    }
}

这样修改后，代码就能够正确地找到数组元素之和等于目标值的索引位置了。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7493902
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：【算法题】输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为o(n)。
• 除此之外, 这篇博客: 归并排序、快速排序和时间复杂度中的 2.对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^