算法学习：数组 - 双指针法

821. 字符的最短距离

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它最近的字符 c 的距离。

两个下标 i 和 j 之间的距离为 abs(i - j) ，其中 abs 是绝对值函数。

背景：字符串

目的：计算与目的字符的距离，保留最短距离

方法：快慢指针

解题思路

暴力解法的思路是这样的：让慢指针找到目标字符c，快指针从下标0开始计算与字符c之间的距离。每找到一个字符c都要重新遍历一遍字符串，并保留最小值。这需要我们初始化一个数组保留我们的结果，并且数组的初始值为一个比较大的值。

直接上代码：

#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    vector<int> shortestToChar(string s, char c)
    {
        int length = s.length();
        vector<int> ans(length, INT16_MAX);
        for (int i = 0; i < length; i++)
        {
            for (int j = 0; s.at(i) == c && j < length; j++)
            {
                ans[j] = std::min(std::abs(i - j), ans[j]);
            }
        }
        return ans;
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    s.shortestToChar("loveleetcode", 'e');
    return 0;
}

两次遍历的思路：一个字符串，从左到右计算一遍最短距离，再从右到左计算一遍最短距离，两次遍历中最小的距离就是我们想要的结果。

使用这种思路，我们可以将复杂度从O(n^2)降低到O(n)。

我们需要一个指针 prev 来保留字符c出现的位置，再用一个指针 i 来遍历字符串。

从左向右遍历时，存储的结果为 i - prev，这样字符c右侧的距离就计算完毕了。在遍历之前，我们需要考虑prev的初始值，这关系到我们能否得到正确的结果。

从左向右遍历时，我们考虑不到字符c左侧的情况，但是我们希望字符c左侧的距离尽可能存储一个最大值，这样在进行从右向左的遍历中，这个最大值会得到正确的更新。

若要让i - prev最大，那么prev最好是一个负值，一个比较合适的负值就是字符串的长度，或者说只要大于这个长度就可以，让我们来验证一下这个想法，考虑一个极端情况：

s = "abcde", c = 'd'

我们让prev的初始值为字符串的长度5，那么经过i - prev之后的结果如何呢？

s = "abcde"
ans = [5,6,7,0,1]

‘abc’三个字符实际上的和‘d’距离，要比数组中记录的小，这样就达到了我们的目的–尽可能的存储一个最大值。

之后我们从右至左遍历，存储的结果为prev - i，这样字符c左侧的距离就计算完毕了，但我们仍然需要考虑prev的初始值。

和从左遍历相反，我们考虑不到c右侧的情况，同样的，我们希望c的右侧计算出一个最大值，这样在和前一次遍历的结果取最小值时，我们能得到正确的结果。

若要让prev - i最大，prev最好是一个极大值，只要让prev - i的结果大于字符串长度即可，这里我们将prev的初始值设为两倍字符串的长度，我们来验证一下这样的想法。

s = "abcde", c = 'a'
ans = [0,9,8,7,6]

上面是一次从右向左遍历的结果，在字符‘a’的右侧，我们确实得到了较大的值，这很好的符合了我们的预期。

最后，我们只需要保留两次遍历中最小的结果即可。

来看看代码：

#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    vector<int> shortestToChar(string s, char c)
    {
        int length = s.length();
        vector<int> ans(length);
        int prev = 0 - length;
        for (int i = 0; i < length; i++)
        {
            if (s.at(i) == c)
            {
                prev = i;
            }
            ans[i] = i - prev;
        }
        prev = 2 * length;
        for (int i = length - 1; i >= 0; i--)
        {
            if (s.at(i) == c)
            {
                prev = i;
            }
            ans[i] = std::min(prev - i, ans[i]);
        }

        return ans;
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    s.shortestToChar("loveleetcode", 'e');
    return 0;
}