528
个编辑
更改
跳到导航
跳到搜索
建立内容为“使用左右两个指针，按一定规则向右移动。注意 window 的大小并不一定是固定的。 == 使用 pattern == 在需要找一个区间的问…”的新页面
使用左右两个指针，按一定规则向右移动。注意 window 的大小并不一定是固定的。
== 使用 pattern ==
在需要找一个区间的问题中，首先移动右指针使得满足要求，再移动左指针直到不满足要求，再移动右指针，持续如此，直到区间的右边界到达整体的结束点。
<ref>[http://www.noteanddata.com/leetcode-3-Longest-Substring-Without-Repeating-Characters-java-sliding-windows-solution-note.html#sliding-windows滑动窗口的特征和基本模版 sliding windows 滑动窗口的特征和基本模版]</ref> <ref>https://blog.csdn.net/fuxuemingzhu/article/details/82931106</ref>
<syntaxhighlight lang=python>
left = 0
ret = worse case retval
for right in range(n):
update state
while state is valid:
sol = f(left, right)
if sol is better than ret:
ret = sol
left += 1
update state
return ret
</syntaxhighlight>
== 相关题目 ==
=== [https://leetcode.com/problems/minimum-window-substring/ LeetCode 76. Minimum Window Substring] ===
Python 解法：
<syntaxhighlight lang=python>
def minWindow(self, s: str, t: str) -> str:
ret = ''
# cnt: how many chars of t has been covered. just for speeding up the algo
cnt = 0
left = 0
min_size = float('inf')
chars = Counter()
target = Counter(t)
for right, sc in enumerate(s):
# for a new right pointer, update the state
chars[sc] += 1
if chars[sc] <= target[sc]:
cnt += 1
# move the left pointer right until the state becomes invalid
while cnt == len(t):
if (size := right - left + 1) < min_size:
min_size = size
ret = s[left:right + 1]
# for a new left pointer, update the state
sl = s[left]
left += 1
chars[sl] -= 1
if chars[sl] < target[sl]:
cnt -= 1
return ret
</syntaxhighlight>
== 参考资料 ==
<references />
[[Category:刷题]]
[[Category:双指针]]
== 使用 pattern ==
在需要找一个区间的问题中，首先移动右指针使得满足要求，再移动左指针直到不满足要求，再移动右指针，持续如此，直到区间的右边界到达整体的结束点。
<ref>[http://www.noteanddata.com/leetcode-3-Longest-Substring-Without-Repeating-Characters-java-sliding-windows-solution-note.html#sliding-windows滑动窗口的特征和基本模版 sliding windows 滑动窗口的特征和基本模版]</ref> <ref>https://blog.csdn.net/fuxuemingzhu/article/details/82931106</ref>
<syntaxhighlight lang=python>
left = 0
ret = worse case retval
for right in range(n):
update state
while state is valid:
sol = f(left, right)
if sol is better than ret:
ret = sol
left += 1
update state
return ret
</syntaxhighlight>
== 相关题目 ==
=== [https://leetcode.com/problems/minimum-window-substring/ LeetCode 76. Minimum Window Substring] ===
Python 解法：
<syntaxhighlight lang=python>
def minWindow(self, s: str, t: str) -> str:
ret = ''
# cnt: how many chars of t has been covered. just for speeding up the algo
cnt = 0
left = 0
min_size = float('inf')
chars = Counter()
target = Counter(t)
for right, sc in enumerate(s):
# for a new right pointer, update the state
chars[sc] += 1
if chars[sc] <= target[sc]:
cnt += 1
# move the left pointer right until the state becomes invalid
while cnt == len(t):
if (size := right - left + 1) < min_size:
min_size = size
ret = s[left:right + 1]
# for a new left pointer, update the state
sl = s[left]
left += 1
chars[sl] -= 1
if chars[sl] < target[sl]:
cnt -= 1
return ret
</syntaxhighlight>
== 参考资料 ==
<references />
[[Category:刷题]]
[[Category:双指针]]