LeetCode 821简单双指针 · 滑窗

字符的最短距离图解题解

这道题到底在问什么

给定字符串 s 和字符 c（c 一定在 s 里出现过）。返回数组 answer，answer 长度等于 s 的长度，answer[i] 是下标 i 到离它最近的字符 c 的距离，距离为 abs(i 减 j)。

输入: s="loveleetcode", c="e"
输出: [3,2,1,0,1,0,0,1,2,2,1,0]
输入: s="aaab", c="b"
输出: [3,2,1,0]　（b 在末尾，越往左越远）

最优解：一步一步想明白

3核心就八个字：左右各扫一遍，取 min。下面每一帧都在套它。
4先把目标字符 e 全找出来:绿色这四个位置(下标 3、5、6、11)本身到 e 的距离都是 0。其余位置的距离，就看它离最近的绿色有多远。
5走到下标 0（字符 l），它左边一个 e 都还没出现，到左边 e 的距离先记成无穷大 ∞，等第二遍从右边补。
6走到下标 1（字符 o），它左边一个 e 都还没出现，到左边 e 的距离先记成无穷大 ∞，等第二遍从右边补。
7走到下标 2（字符 v），它左边一个 e 都还没出现，到左边 e 的距离先记成无穷大 ∞，等第二遍从右边补。
8走到下标 3，正好是 e。它本身距离为 0，同时把 pre 记成 3，往后的位置就拿它当「左边最近的 e」。
9走到下标 4（字符 l），左边最近的 e 在 3，距离就是 4 减 3 等于 1。
10走到下标 5，正好是 e。它本身距离为 0，同时把 pre 记成 5，往后的位置就拿它当「左边最近的 e」。
11走到下标 6，正好是 e。它本身距离为 0，同时把 pre 记成 6，往后的位置就拿它当「左边最近的 e」。
12走到下标 7（字符 t），左边最近的 e 在 6，距离就是 7 减 6 等于 1。
13走到下标 8（字符 c），左边最近的 e 在 6，距离就是 8 减 6 等于 2。
14走到下标 9（字符 o），左边最近的 e 在 6，距离就是 9 减 6 等于 3。
15走到下标 10（字符 d），左边最近的 e 在 6，距离就是 10 减 6 等于 4。
16走到下标 11，正好是 e。它本身距离为 0，同时把 pre 记成 11，往后的位置就拿它当「左边最近的 e」。
17第一遍扫完了。每个位置都拿到了「到左边最近 e」的距离。注意开头 lov 三个位置还是 ∞，因为它们左边根本没有 e。这正是要扫第二遍的原因。
18从右往左走到下标 11，又是 e，把 suf 记成 11，它本身答案就是 0。
19走到下标 10，右边最近的 e 在 11，右距 1。和第一遍的左距 4 比，取小的：答案 = 1。右边更近，更新成它。
20走到下标 9，右边最近的 e 在 11，右距 2。和第一遍的左距 3 比，取小的：答案 = 2。右边更近，更新成它。
21走到下标 8，右边最近的 e 在 11，右距 3。和第一遍的左距 2 比，取小的：答案 = 2。左边本来就更近，保持不变。
22走到下标 7，右边最近的 e 在 11，右距 4。和第一遍的左距 1 比，取小的：答案 = 1。左边本来就更近，保持不变。
23从右往左走到下标 6，又是 e，把 suf 记成 6，它本身答案就是 0。
24从右往左走到下标 5，又是 e，把 suf 记成 5，它本身答案就是 0。
25走到下标 4，右边最近的 e 在 5，右距 1。和第一遍的左距 1 比，取小的：答案 = 1。左右一样近，取最小还是 1，答案保持不变。
26从右往左走到下标 3，又是 e，把 suf 记成 3，它本身答案就是 0。
27走到下标 2，右边最近的 e 在 3，右距 1。和第一遍的左距 ∞ 比，取小的：答案 = 1。右边更近，更新成它。
28走到下标 1，右边最近的 e 在 3，右距 2。和第一遍的左距 ∞ 比，取小的：答案 = 2。右边更近，更新成它。
29走到下标 0，右边最近的 e 在 3，右距 3。和第一遍的左距 ∞ 比，取小的：答案 = 3。右边更近，更新成它。
30两遍合起来,每个位置都拿到了「左边最近」和「右边最近」里更小的那个,这就是到最近 e 的真实距离。最终答案 [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0],和题目给的输出完全一致。

⚠️ 容易写错的地方

✗ 错：只扫一遍就交答案

✓ 对：必须左右各扫一遍取 min

一遍只能拿到一侧最近的 c，开头或结尾那些位置会算错

✗ 错：第一遍 pre 没遇到 c 时用 0

✓ 对：应记成无穷大 ∞

左边没有 c 就不该有左距，记 0 会把答案压成错的 0

✗ 错：把距离写成带正负的差

✓ 对：距离是 abs，恒为非负

两遍分别用 i 减 pre、suf 减 i，方向保证了都是非负，不要再带符号

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [n] * n
        pre = -inf
        for i, ch in enumerate(s):
            if ch == c:
                pre = i
            ans[i] = min(ans[i], i - pre)
        suf = inf
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                suf = i
            ans[i] = min(ans[i], suf - i)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        const int inf = 1 << 30;
        vector<int> ans(n, inf);
        for (int i = 0, pre = -inf; i < n; ++i) {
            if (s[i] == c) {
                pre = i;
            }
            ans[i] = min(ans[i], i - pre);
        }
        for (int i = n - 1, suf = inf; ~i; --i) {
            if (s[i] == c) {
                suf = i;
            }
            ans[i] = min(ans[i], suf - i);
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        final int inf = 1 << 30;
        Arrays.fill(ans, inf);
        for (int i = 0, pre = -inf; i < n; ++i) {
            if (s.charAt(i) == c) {
                pre = i;
            }
            ans[i] = Math.min(ans[i], i - pre);
        }
        for (int i = n - 1, suf = inf; i >= 0; --i) {
            if (s.charAt(i) == c) {
                suf = i;
            }
            ans[i] = Math.min(ans[i], suf - i);
        }
        return ans;
    }
}

复杂度

时间

O(n)

从左扫一遍 + 从右扫一遍，共两遍线性

空间

O(1)

除答案数组外，只用 pre、suf 两个变量（答案数组是必须的输出）

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着字符的最短距离的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

能不能只用一遍扫描解决？+

单纯一遍不行，因为扫到某个位置时，它右边的 c 你还没看到。可以换个思路:先把所有 c 的下标收集起来，再对每个位置二分查找左右最近的 c 取 min，那是 O(n log m)，反而比两遍 O(n) 慢。所以两遍线性是最简洁的写法。

如果 c 在串里一次都不出现会怎样？+

本题保证 c 至少出现一次，所以不用处理。但若题目放开这个保证，第一遍和第二遍都不会更新 pre、suf，答案数组会全是初始的那个大数，这时应按约定返回空或全 ∞，要和面试官确认口径。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把字符的最短距离一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 821简单双指针 · 滑窗

字符的最短距离图解题解

这道题到底在问什么

输入: s="loveleetcode", c="e"
输出: [3,2,1,0,1,0,0,1,2,2,1,0]
输入: s="aaab", c="b"
输出: [3,2,1,0]　（b 在末尾，越往左越远）

最优解：一步一步想明白

3核心就八个字：左右各扫一遍，取 min。下面每一帧都在套它。
4先把目标字符 e 全找出来:绿色这四个位置(下标 3、5、6、11)本身到 e 的距离都是 0。其余位置的距离，就看它离最近的绿色有多远。
5走到下标 0（字符 l），它左边一个 e 都还没出现，到左边 e 的距离先记成无穷大 ∞，等第二遍从右边补。
6走到下标 1（字符 o），它左边一个 e 都还没出现，到左边 e 的距离先记成无穷大 ∞，等第二遍从右边补。
7走到下标 2（字符 v），它左边一个 e 都还没出现，到左边 e 的距离先记成无穷大 ∞，等第二遍从右边补。
8走到下标 3，正好是 e。它本身距离为 0，同时把 pre 记成 3，往后的位置就拿它当「左边最近的 e」。
9走到下标 4（字符 l），左边最近的 e 在 3，距离就是 4 减 3 等于 1。
10走到下标 5，正好是 e。它本身距离为 0，同时把 pre 记成 5，往后的位置就拿它当「左边最近的 e」。
11走到下标 6，正好是 e。它本身距离为 0，同时把 pre 记成 6，往后的位置就拿它当「左边最近的 e」。
12走到下标 7（字符 t），左边最近的 e 在 6，距离就是 7 减 6 等于 1。
13走到下标 8（字符 c），左边最近的 e 在 6，距离就是 8 减 6 等于 2。
14走到下标 9（字符 o），左边最近的 e 在 6，距离就是 9 减 6 等于 3。
15走到下标 10（字符 d），左边最近的 e 在 6，距离就是 10 减 6 等于 4。
16走到下标 11，正好是 e。它本身距离为 0，同时把 pre 记成 11，往后的位置就拿它当「左边最近的 e」。
17第一遍扫完了。每个位置都拿到了「到左边最近 e」的距离。注意开头 lov 三个位置还是 ∞，因为它们左边根本没有 e。这正是要扫第二遍的原因。
18从右往左走到下标 11，又是 e，把 suf 记成 11，它本身答案就是 0。
19走到下标 10，右边最近的 e 在 11，右距 1。和第一遍的左距 4 比，取小的：答案 = 1。右边更近，更新成它。
20走到下标 9，右边最近的 e 在 11，右距 2。和第一遍的左距 3 比，取小的：答案 = 2。右边更近，更新成它。
21走到下标 8，右边最近的 e 在 11，右距 3。和第一遍的左距 2 比，取小的：答案 = 2。左边本来就更近，保持不变。
22走到下标 7，右边最近的 e 在 11，右距 4。和第一遍的左距 1 比，取小的：答案 = 1。左边本来就更近，保持不变。
23从右往左走到下标 6，又是 e，把 suf 记成 6，它本身答案就是 0。
24从右往左走到下标 5，又是 e，把 suf 记成 5，它本身答案就是 0。
25走到下标 4，右边最近的 e 在 5，右距 1。和第一遍的左距 1 比，取小的：答案 = 1。左右一样近，取最小还是 1，答案保持不变。
26从右往左走到下标 3，又是 e，把 suf 记成 3，它本身答案就是 0。
27走到下标 2，右边最近的 e 在 3，右距 1。和第一遍的左距 ∞ 比，取小的：答案 = 1。右边更近，更新成它。
28走到下标 1，右边最近的 e 在 3，右距 2。和第一遍的左距 ∞ 比，取小的：答案 = 2。右边更近，更新成它。
29走到下标 0，右边最近的 e 在 3，右距 3。和第一遍的左距 ∞ 比，取小的：答案 = 3。右边更近，更新成它。
30两遍合起来,每个位置都拿到了「左边最近」和「右边最近」里更小的那个,这就是到最近 e 的真实距离。最终答案 [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0],和题目给的输出完全一致。

⚠️ 容易写错的地方

✗ 错：只扫一遍就交答案

✓ 对：必须左右各扫一遍取 min

一遍只能拿到一侧最近的 c，开头或结尾那些位置会算错

✗ 错：第一遍 pre 没遇到 c 时用 0

✓ 对：应记成无穷大 ∞

左边没有 c 就不该有左距，记 0 会把答案压成错的 0

✗ 错：把距离写成带正负的差

✓ 对：距离是 abs，恒为非负

两遍分别用 i 减 pre、suf 减 i，方向保证了都是非负，不要再带符号

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [n] * n
        pre = -inf
        for i, ch in enumerate(s):
            if ch == c:
                pre = i
            ans[i] = min(ans[i], i - pre)
        suf = inf
        for i in range(n - 1, -1, -1):
            if s[i] == c:
                suf = i
            ans[i] = min(ans[i], suf - i)
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.size();
        const int inf = 1 << 30;
        vector<int> ans(n, inf);
        for (int i = 0, pre = -inf; i < n; ++i) {
            if (s[i] == c) {
                pre = i;
            }
            ans[i] = min(ans[i], i - pre);
        }
        for (int i = n - 1, suf = inf; ~i; --i) {
            if (s[i] == c) {
                suf = i;
            }
            ans[i] = min(ans[i], suf - i);
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        final int inf = 1 << 30;
        Arrays.fill(ans, inf);
        for (int i = 0, pre = -inf; i < n; ++i) {
            if (s.charAt(i) == c) {
                pre = i;
            }
            ans[i] = Math.min(ans[i], i - pre);
        }
        for (int i = n - 1, suf = inf; i >= 0; --i) {
            if (s.charAt(i) == c) {
                suf = i;
            }
            ans[i] = Math.min(ans[i], suf - i);
        }
        return ans;
    }
}

复杂度

时间

O(n)

从左扫一遍 + 从右扫一遍，共两遍线性

空间

O(1)

除答案数组外，只用 pre、suf 两个变量（答案数组是必须的输出）

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着字符的最短距离的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

能不能只用一遍扫描解决？+

如果 c 在串里一次都不出现会怎样？+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

字符的最短距离 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

字符的最短距离 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

字符的最短距离图解题解

字符的最短距离图解题解