时间戳

首页 > 解决方案 > 澄清两个指针方法的工作

c++ - 澄清两个指针方法的工作

问题描述

我对使用两个指针方法有一些疑问。

情况 1： - 假设我们有一个已排序的数组 A 和一个目标值 B。我们想找出是否存在两个差值等于 B 的元素。

int helper(vector<int> &A, int B)
{
    int left = 0, n = A.size();
    int right = left + 1;
    while (right < n)
    {
        int currDiff = A[right] - A[left];
        if (currDiff < B)
            right++;
        else if (currDiff > B)
        {
            left++;
            if (left == right)
                right++;
        }
        else
            return 1;
    }
    return 0;
}

情况 2： - 假设我们有一个已排序的数组 A 和一个目标值 B。我们想找出是否存在两个总和等于 B 的元素。

int helper(vector<int> &A, int B)
{
    int left = 0, n = A.size();
    int right = n - 1;
    while (left < right)
    {
        int currSum = A[right] + A[left];
        if (currSum < B)
            left++;
        else if (currSum > B)
        {
            right--;
        }
        else
            return 1;
    }
    return 0;
}

值得怀疑的是，在情况 1 中，我们将两个指针都设置在左侧（left = 0, right = left + 1）并开始扫描，而在情况 2 中，我们将一个指针设置在左侧，另一个指针设置在右侧（left = 0, right = A.size() - 1）。

我对这是如何工作的有点困惑。

标签： c++algorithm

解决方案

没有规定您必须以不同的方式设置两个指针。这完全取决于您所遵循的算法。这可能是好的，也可能是坏的。比方说，为了区别，我们设置了left=0and right=A.size()-1。当给定数组排序时，和A之间的第一个差异将是最大的。A[right]A[left]

    int currDiff = A[right] - A[left];    //max possible value for currDiff for A

那么，现在如果currDiff大于给定的数字，你会怎么做？增加left或减少right？假设你做后面的，我的意思是减少right，并且相应的条件再次满足，做同样的事情，减少right。现在，假设现在你得到的currDiff小于给定的数字，你会怎么做？增加left? 大概。但是在下一次迭代中，如果满足同样的条件，也currDiff就是仍然小于给定的数，那现在怎么办？再次增加left? 如果right在这个特定位置增加 会给你带来结果怎么办？

finding diff of pair所以，你看，如果你开始在相反的两端有左右，就会出现很多需要处理的情况。

最后，我想说的是，这一切都与您遵循的算法有关，仅此而已。

推荐阅读