flykhan/maths-cs-ai-compendium-zh
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
gh-pages
maths-cs-ai-compendium-zh/chapter 14: data structures and algorithms/01. arrays and hashing/index.html
T

6363 lines
164 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="zh" class="no-js">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<meta name="description" content="一本开源的直觉优先教科书，从零开始覆盖数学、计算机科学和人工智能（中文翻译版）。">
<meta name="author" content="Henry Ndubuaku (flykhan 译)">
<link rel="canonical" href="https://flykhan.github.io/maths-cs-ai-compendium-zh/chapter%2014%3A%20data%20structures%20and%20algorithms/01.%20arrays%20and%20hashing/">
<link rel="prev" href="../00.%20foundations/">
<link rel="next" href="../02.%20linked%20lists%2C%20stacks%2C%20and%20queues/">
<link rel="icon" href="../../assets/images/favicon.png">
<meta name="generator" content="mkdocs-1.6.1, mkdocs-material-9.7.6">
<title>数组与哈希 - 数学、计算机科学与 AI 百科全书</title>
<link rel="stylesheet" href="../../assets/stylesheets/main.484c7ddc.min.css">
<link rel="stylesheet" href="../../assets/stylesheets/palette.ab4e12ef.min.css">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,300i,400,400i,700,700i%7CRoboto+Mono:400,400i,700,700i&display=fallback">
<style>:root{--md-text-font:"Roboto";--md-code-font:"Roboto Mono"}</style>
<script>__md_scope=new URL("../..",location),__md_hash=e=>[...e].reduce(((e,_)=>(e<<5)-e+_.charCodeAt(0)),0),__md_get=(e,_=localStorage,t=__md_scope)=>JSON.parse(_.getItem(t.pathname+"."+e)),__md_set=(e,_,t=localStorage,a=__md_scope)=>{try{t.setItem(a.pathname+"."+e,JSON.stringify(_))}catch(e){}}</script>
</head>
<body dir="ltr" data-md-color-scheme="default" data-md-color-primary="slate" data-md-color-accent="indigo">
<input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
<input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
<label class="md-overlay" for="__drawer"></label>
<div data-md-component="skip">
<a href="#_1" class="md-skip">
跳转至
</a>
</div>
<div data-md-component="announce">
</div>
<header class="md-header" data-md-component="header">
<nav class="md-header__inner md-grid" aria-label="页眉">
<a href="../.." title="数学、计算机科学与 AI 百科全书" class="md-header__button md-logo" aria-label="数学、计算机科学与 AI 百科全书" data-md-component="logo">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 0 0 3-3 3 3 0 0 0-3-3 3 3 0 0 0-3 3 3 3 0 0 0 3 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54"/></svg>
</a>
<label class="md-header__button md-icon" for="__drawer">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M3 6h18v2H3zm0 5h18v2H3zm0 5h18v2H3z"/></svg>
</label>
<div class="md-header__title" data-md-component="header-title">
<div class="md-header__ellipsis">
<div class="md-header__topic">
<span class="md-ellipsis">
数学、计算机科学与 AI 百科全书
</span>
</div>
<div class="md-header__topic" data-md-component="header-topic">
<span class="md-ellipsis">
数组与哈希
</span>
</div>
</div>
</div>
<form class="md-header__option" data-md-component="palette">
<input class="md-option" data-md-color-media="" data-md-color-scheme="default" data-md-color-primary="slate" data-md-color-accent="indigo" aria-label="切换到深色模式" type="radio" name="__palette" id="__palette_0">
<label class="md-header__button md-icon" title="切换到深色模式" for="__palette_1" hidden>
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a4 4 0 0 0-4 4 4 4 0 0 0 4 4 4 4 0 0 0 4-4 4 4 0 0 0-4-4m0 10a6 6 0 0 1-6-6 6 6 0 0 1 6-6 6 6 0 0 1 6 6 6 6 0 0 1-6 6m8-9.31V4h-4.69L12 .69 8.69 4H4v4.69L.69 12 4 15.31V20h4.69L12 23.31 15.31 20H20v-4.69L23.31 12z"/></svg>
</label>
<input class="md-option" data-md-color-media="" data-md-color-scheme="slate" data-md-color-primary="slate" data-md-color-accent="indigo" aria-label="切换到浅色模式" type="radio" name="__palette" id="__palette_1">
<label class="md-header__button md-icon" title="切换到浅色模式" for="__palette_0" hidden>
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 18c-.89 0-1.74-.2-2.5-.55C11.56 16.5 13 14.42 13 12s-1.44-4.5-3.5-5.45C10.26 6.2 11.11 6 12 6a6 6 0 0 1 6 6 6 6 0 0 1-6 6m8-9.31V4h-4.69L12 .69 8.69 4H4v4.69L.69 12 4 15.31V20h4.69L12 23.31 15.31 20H20v-4.69L23.31 12z"/></svg>
</label>
</form>
<script>var palette=__md_get("__palette");if(palette&&palette.color){if("(prefers-color-scheme)"===palette.color.media){var media=matchMedia("(prefers-color-scheme: light)"),input=document.querySelector(media.matches?"[data-md-color-media='(prefers-color-scheme: light)']":"[data-md-color-media='(prefers-color-scheme: dark)']");palette.color.media=input.getAttribute("data-md-color-media"),palette.color.scheme=input.getAttribute("data-md-color-scheme"),palette.color.primary=input.getAttribute("data-md-color-primary"),palette.color.accent=input.getAttribute("data-md-color-accent")}for(var[key,value]of Object.entries(palette.color))document.body.setAttribute("data-md-color-"+key,value)}</script>
<label class="md-header__button md-icon" for="__search">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0 1 16 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.52 6.52 0 0 1 9.5 16 6.5 6.5 0 0 1 3 9.5 6.5 6.5 0 0 1 9.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5"/></svg>
</label>
<div class="md-search" data-md-component="search" role="dialog">
<label class="md-search__overlay" for="__search"></label>
<div class="md-search__inner" role="search">
<form class="md-search__form" name="search">
<input type="text" class="md-search__input" name="query" aria-label="搜索" placeholder="搜索" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="search-query" required>
<label class="md-search__icon md-icon" for="__search">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0 1 16 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.52 6.52 0 0 1 9.5 16 6.5 6.5 0 0 1 3 9.5 6.5 6.5 0 0 1 9.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5"/></svg>
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11z"/></svg>
</label>
<nav class="md-search__options" aria-label="查找">
<button type="reset" class="md-search__icon md-icon" title="清空当前内容" aria-label="清空当前内容" tabindex="-1">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M19 6.41 17.59 5 12 10.59 6.41 5 5 6.41 10.59 12 5 17.59 6.41 19 12 13.41 17.59 19 19 17.59 13.41 12z"/></svg>
</button>
</nav>
<div class="md-search__suggest" data-md-component="search-suggest"></div>
</form>
<div class="md-search__output">
<div class="md-search__scrollwrap" tabindex="0" data-md-scrollfix>
<div class="md-search-result" data-md-component="search-result">
<div class="md-search-result__meta">
正在初始化搜索引擎
</div>
<ol class="md-search-result__list" role="presentation"></ol>
</div>
</div>
</div>
</div>
</div>
<div class="md-header__source">
<a href="https://github.com/flykhan/maths-cs-ai-compendium-zh" title="前往仓库" class="md-source" data-md-component="source">
<div class="md-source__icon md-icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><!--! Font Awesome Free 7.1.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2025 Fonticons, Inc.--><path d="M439.6 236.1 244 40.5c-5.4-5.5-12.8-8.5-20.4-8.5s-15 3-20.4 8.4L162.5 81l51.5 51.5c27.1-9.1 52.7 16.8 43.4 43.7l49.7 49.7c34.2-11.8 61.2 31 35.5 56.7-26.5 26.5-70.2-2.9-56-37.3L240.3 199v121.9c25.3 12.5 22.3 41.8 9.1 55-6.4 6.4-15.2 10.1-24.3 10.1s-17.8-3.6-24.3-10.1c-17.6-17.6-11.1-46.9 11.2-56v-123c-20.8-8.5-24.6-30.7-18.6-45L142.6 101 8.5 235.1C3 240.6 0 247.9 0 255.5s3 15 8.5 20.4l195.6 195.7c5.4 5.4 12.7 8.4 20.4 8.4s15-3 20.4-8.4l194.7-194.7c5.4-5.4 8.4-12.8 8.4-20.4s-3-15-8.4-20.4"/></svg>
</div>
<div class="md-source__repository">
flykhan/maths-cs-ai-compendium-zh
</div>
</a>
</div>
</nav>
</header>
<div class="md-container" data-md-component="container">
<nav class="md-tabs" aria-label="标签" data-md-component="tabs">
<div class="md-grid">
<ul class="md-tabs__list">
<li class="md-tabs__item">
<a href="../.." class="md-tabs__link">
首页
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2001%3A%20vectors/01.%20vector%20spaces/" class="md-tabs__link">
向量
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2002%3A%20matrices/01.%20matrix%20properties/" class="md-tabs__link">
矩阵
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2003%3A%20calculus/01.%20differential%20calculus/" class="md-tabs__link">
微积分
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2004%3A%20statistics/01.%20fundamentals/" class="md-tabs__link">
统计学
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2005%3A%20probability/01.%20counting/" class="md-tabs__link">
概率论
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2006%3A%20machine%20learning/01.%20classical%20machine%20learning/" class="md-tabs__link">
机器学习
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2007%3A%20computational%20linguistics/01.%20linguistic%20foundations/" class="md-tabs__link">
计算语言学
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2008%3A%20computer%20vision/01.%20image%20fundamentals/" class="md-tabs__link">
计算机视觉
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2009%3A%20audio%20and%20speech/01.%20digital%20signal%20processing/" class="md-tabs__link">
音频与语音
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2010%3A%20multimodal%20learning/01.%20multimodal%20representations/" class="md-tabs__link">
多模态学习
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2011%3A%20autonomous%20systems/01.%20perception/" class="md-tabs__link">
自主系统
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2012%3A%20graph%20neural%20networks/01.%20geometric%20deep%20learning/" class="md-tabs__link">
图神经网络
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2013%3A%20computing%20and%20OS/01.%20discrete%20maths/" class="md-tabs__link">
计算机与操作系统
</a>
</li>
<li class="md-tabs__item md-tabs__item--active">
<a href="../00.%20foundations/" class="md-tabs__link">
数据结构与算法
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2015%3A%20production%20software%20engineering/01.%20linux%20and%20CMD/" class="md-tabs__link">
生产级软件工程
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/00.%20why%20C%2B%2B%20and%20how%20ML%20frameworks%20work/" class="md-tabs__link">
SIMD 与 GPU 编程
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2017%3A%20AI%20inference/01.%20quantisation/" class="md-tabs__link">
AI 推理
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2018%3A%20ML%20systems%20design/01.%20systems%20design%20fundamentals/" class="md-tabs__link">
ML 系统设计
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2019%3A%20applied%20AI/01.%20AI%20for%20finance/" class="md-tabs__link">
应用 AI
</a>
</li>
<li class="md-tabs__item">
<a href="../../chapter%2020%3A%20bleeding%20edge%20AI/01.%20quantum%20machine%20learning/" class="md-tabs__link">
前沿 AI
</a>
</li>
</ul>
</div>
</nav>
<main class="md-main" data-md-component="main">
<div class="md-main__inner md-grid">
<div class="md-sidebar md-sidebar--primary" data-md-component="sidebar" data-md-type="navigation" >
<div class="md-sidebar__scrollwrap">
<div class="md-sidebar__inner">
<nav class="md-nav md-nav--primary md-nav--lifted" aria-label="导航栏" data-md-level="0">
<label class="md-nav__title" for="__drawer">
<a href="../.." title="数学、计算机科学与 AI 百科全书" class="md-nav__button md-logo" aria-label="数学、计算机科学与 AI 百科全书" data-md-component="logo">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M12 8a3 3 0 0 0 3-3 3 3 0 0 0-3-3 3 3 0 0 0-3 3 3 3 0 0 0 3 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54"/></svg>
</a>
数学、计算机科学与 AI 百科全书
</label>
<div class="md-nav__source">
<a href="https://github.com/flykhan/maths-cs-ai-compendium-zh" title="前往仓库" class="md-source" data-md-component="source">
<div class="md-source__icon md-icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><!--! Font Awesome Free 7.1.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2025 Fonticons, Inc.--><path d="M439.6 236.1 244 40.5c-5.4-5.5-12.8-8.5-20.4-8.5s-15 3-20.4 8.4L162.5 81l51.5 51.5c27.1-9.1 52.7 16.8 43.4 43.7l49.7 49.7c34.2-11.8 61.2 31 35.5 56.7-26.5 26.5-70.2-2.9-56-37.3L240.3 199v121.9c25.3 12.5 22.3 41.8 9.1 55-6.4 6.4-15.2 10.1-24.3 10.1s-17.8-3.6-24.3-10.1c-17.6-17.6-11.1-46.9 11.2-56v-123c-20.8-8.5-24.6-30.7-18.6-45L142.6 101 8.5 235.1C3 240.6 0 247.9 0 255.5s3 15 8.5 20.4l195.6 195.7c5.4 5.4 12.7 8.4 20.4 8.4s15-3 20.4-8.4l194.7-194.7c5.4-5.4 8.4-12.8 8.4-20.4s-3-15-8.4-20.4"/></svg>
</div>
<div class="md-source__repository">
flykhan/maths-cs-ai-compendium-zh
</div>
</a>
</div>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../.." class="md-nav__link">
<span class="md-ellipsis">
首页
</span>
</a>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_2" >
<label class="md-nav__link" for="__nav_2" id="__nav_2_label" tabindex="0">
<span class="md-ellipsis">
向量
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_2_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_2">
<span class="md-nav__icon md-icon"></span>
向量
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2001%3A%20vectors/01.%20vector%20spaces/" class="md-nav__link">
<span class="md-ellipsis">
向量空间
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2001%3A%20vectors/02.%20vector%20properties/" class="md-nav__link">
<span class="md-ellipsis">
向量性质
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2001%3A%20vectors/03.%20norms%20and%20metrics/" class="md-nav__link">
<span class="md-ellipsis">
范数与度量
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2001%3A%20vectors/04.%20products/" class="md-nav__link">
<span class="md-ellipsis">
向量积
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2001%3A%20vectors/05.%20basis%20and%20duality/" class="md-nav__link">
<span class="md-ellipsis">
基与对偶性
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_3" >
<label class="md-nav__link" for="__nav_3" id="__nav_3_label" tabindex="0">
<span class="md-ellipsis">
矩阵
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_3_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_3">
<span class="md-nav__icon md-icon"></span>
矩阵
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2002%3A%20matrices/01.%20matrix%20properties/" class="md-nav__link">
<span class="md-ellipsis">
矩阵性质
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2002%3A%20matrices/02.%20matrix%20types/" class="md-nav__link">
<span class="md-ellipsis">
矩阵类型
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2002%3A%20matrices/03.%20operations/" class="md-nav__link">
<span class="md-ellipsis">
矩阵运算
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2002%3A%20matrices/04.%20linear%20transformations/" class="md-nav__link">
<span class="md-ellipsis">
线性变换
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2002%3A%20matrices/05.%20decompositions/" class="md-nav__link">
<span class="md-ellipsis">
矩阵分解
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_4" >
<label class="md-nav__link" for="__nav_4" id="__nav_4_label" tabindex="0">
<span class="md-ellipsis">
微积分
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_4_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_4">
<span class="md-nav__icon md-icon"></span>
微积分
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2003%3A%20calculus/01.%20differential%20calculus/" class="md-nav__link">
<span class="md-ellipsis">
微分
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2003%3A%20calculus/02.%20integral%20calculus/" class="md-nav__link">
<span class="md-ellipsis">
积分
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2003%3A%20calculus/03.%20multivariate%20calculus/" class="md-nav__link">
<span class="md-ellipsis">
多元微积分
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2003%3A%20calculus/04.%20function%20approximation/" class="md-nav__link">
<span class="md-ellipsis">
函数逼近
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2003%3A%20calculus/05.%20optimisation/" class="md-nav__link">
<span class="md-ellipsis">
优化
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_5" >
<label class="md-nav__link" for="__nav_5" id="__nav_5_label" tabindex="0">
<span class="md-ellipsis">
统计学
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_5_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_5">
<span class="md-nav__icon md-icon"></span>
统计学
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2004%3A%20statistics/01.%20fundamentals/" class="md-nav__link">
<span class="md-ellipsis">
基础
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2004%3A%20statistics/02.%20measures/" class="md-nav__link">
<span class="md-ellipsis">
统计量
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2004%3A%20statistics/03.%20sampling/" class="md-nav__link">
<span class="md-ellipsis">
抽样
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2004%3A%20statistics/04.%20hypothesis%20testing/" class="md-nav__link">
<span class="md-ellipsis">
假设检验
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2004%3A%20statistics/05.%20inference/" class="md-nav__link">
<span class="md-ellipsis">
推断
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_6" >
<label class="md-nav__link" for="__nav_6" id="__nav_6_label" tabindex="0">
<span class="md-ellipsis">
概率论
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_6_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_6">
<span class="md-nav__icon md-icon"></span>
概率论
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2005%3A%20probability/01.%20counting/" class="md-nav__link">
<span class="md-ellipsis">
计数
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2005%3A%20probability/02.%20probability%20concepts/" class="md-nav__link">
<span class="md-ellipsis">
概率概念
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2005%3A%20probability/03.%20distributions/" class="md-nav__link">
<span class="md-ellipsis">
分布
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2005%3A%20probability/04.%20bayesian/" class="md-nav__link">
<span class="md-ellipsis">
贝叶斯
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2005%3A%20probability/05.%20information%20theory/" class="md-nav__link">
<span class="md-ellipsis">
信息论
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_7" >
<label class="md-nav__link" for="__nav_7" id="__nav_7_label" tabindex="0">
<span class="md-ellipsis">
机器学习
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_7_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_7">
<span class="md-nav__icon md-icon"></span>
机器学习
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2006%3A%20machine%20learning/01.%20classical%20machine%20learning/" class="md-nav__link">
<span class="md-ellipsis">
经典机器学习
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2006%3A%20machine%20learning/02.%20gradient%20machine%20learning/" class="md-nav__link">
<span class="md-ellipsis">
梯度机器学习
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2006%3A%20machine%20learning/03.%20deep%20learning/" class="md-nav__link">
<span class="md-ellipsis">
深度学习
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2006%3A%20machine%20learning/04.%20reinforcement%20learning/" class="md-nav__link">
<span class="md-ellipsis">
强化学习
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2006%3A%20machine%20learning/05.%20distributed%20deep%20learning/" class="md-nav__link">
<span class="md-ellipsis">
分布式深度学习
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_8" >
<label class="md-nav__link" for="__nav_8" id="__nav_8_label" tabindex="0">
<span class="md-ellipsis">
计算语言学
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_8_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_8">
<span class="md-nav__icon md-icon"></span>
计算语言学
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2007%3A%20computational%20linguistics/01.%20linguistic%20foundations/" class="md-nav__link">
<span class="md-ellipsis">
语言学基础
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2007%3A%20computational%20linguistics/02.%20text%20processing%20and%20classic%20NLP/" class="md-nav__link">
<span class="md-ellipsis">
文本处理与经典 NLP
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2007%3A%20computational%20linguistics/03.%20embeddings%20and%20sequence%20models/" class="md-nav__link">
<span class="md-ellipsis">
嵌入与序列模型
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2007%3A%20computational%20linguistics/04.%20transformers%20and%20language%20models/" class="md-nav__link">
<span class="md-ellipsis">
Transformer 与语言模型
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2007%3A%20computational%20linguistics/05.%20advanced%20text%20generation/" class="md-nav__link">
<span class="md-ellipsis">
高级文本生成
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_9" >
<label class="md-nav__link" for="__nav_9" id="__nav_9_label" tabindex="0">
<span class="md-ellipsis">
计算机视觉
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_9_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_9">
<span class="md-nav__icon md-icon"></span>
计算机视觉
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2008%3A%20computer%20vision/01.%20image%20fundamentals/" class="md-nav__link">
<span class="md-ellipsis">
图像基础
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2008%3A%20computer%20vision/02.%20convolutional%20networks/" class="md-nav__link">
<span class="md-ellipsis">
卷积网络
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2008%3A%20computer%20vision/03.%20object%20detection%20and%20segmentation/" class="md-nav__link">
<span class="md-ellipsis">
目标检测与分割
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2008%3A%20computer%20vision/04.%20vision%20transformers%20and%20generation/" class="md-nav__link">
<span class="md-ellipsis">
ViT 与生成模型
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2008%3A%20computer%20vision/05.%20video%20and%203D%20vision/" class="md-nav__link">
<span class="md-ellipsis">
视频与 3D 视觉
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_10" >
<label class="md-nav__link" for="__nav_10" id="__nav_10_label" tabindex="0">
<span class="md-ellipsis">
音频与语音
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_10_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_10">
<span class="md-nav__icon md-icon"></span>
音频与语音
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2009%3A%20audio%20and%20speech/01.%20digital%20signal%20processing/" class="md-nav__link">
<span class="md-ellipsis">
数字信号处理
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2009%3A%20audio%20and%20speech/02.%20automatic%20speech%20recognition/" class="md-nav__link">
<span class="md-ellipsis">
自动语音识别
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2009%3A%20audio%20and%20speech/03.%20text%20to%20speech%20and%20voice/" class="md-nav__link">
<span class="md-ellipsis">
语音合成
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2009%3A%20audio%20and%20speech/04.%20speaker%20and%20audio%20analysis/" class="md-nav__link">
<span class="md-ellipsis">
说话人与音频分析
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2009%3A%20audio%20and%20speech/05.%20source%20separation%20and%20noise/" class="md-nav__link">
<span class="md-ellipsis">
源分离与降噪
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_11" >
<label class="md-nav__link" for="__nav_11" id="__nav_11_label" tabindex="0">
<span class="md-ellipsis">
多模态学习
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_11_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_11">
<span class="md-nav__icon md-icon"></span>
多模态学习
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2010%3A%20multimodal%20learning/01.%20multimodal%20representations/" class="md-nav__link">
<span class="md-ellipsis">
多模态表征
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2010%3A%20multimodal%20learning/02.%20vision%20language%20models/" class="md-nav__link">
<span class="md-ellipsis">
视觉语言模型
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2010%3A%20multimodal%20learning/03.%20image%20and%20video%20tokenisation/" class="md-nav__link">
<span class="md-ellipsis">
图像与视频 Token 化
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2010%3A%20multimodal%20learning/04.%20cross-modal%20generation/" class="md-nav__link">
<span class="md-ellipsis">
跨模态生成
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2010%3A%20multimodal%20learning/05.%20unified%20multimodal%20architectures/" class="md-nav__link">
<span class="md-ellipsis">
统一多模态架构
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_12" >
<label class="md-nav__link" for="__nav_12" id="__nav_12_label" tabindex="0">
<span class="md-ellipsis">
自主系统
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_12_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_12">
<span class="md-nav__icon md-icon"></span>
自主系统
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2011%3A%20autonomous%20systems/01.%20perception/" class="md-nav__link">
<span class="md-ellipsis">
感知
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2011%3A%20autonomous%20systems/02.%20robot%20learning/" class="md-nav__link">
<span class="md-ellipsis">
机器人学习
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2011%3A%20autonomous%20systems/03.%20vision-language-action%20models/" class="md-nav__link">
<span class="md-ellipsis">
视觉-语言-动作模型
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2011%3A%20autonomous%20systems/04.%20self-driving/" class="md-nav__link">
<span class="md-ellipsis">
自动驾驶
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2011%3A%20autonomous%20systems/05.%20space%20and%20extreme%20robotics/" class="md-nav__link">
<span class="md-ellipsis">
太空与极端机器人
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_13" >
<label class="md-nav__link" for="__nav_13" id="__nav_13_label" tabindex="0">
<span class="md-ellipsis">
图神经网络
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_13_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_13">
<span class="md-nav__icon md-icon"></span>
图神经网络
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2012%3A%20graph%20neural%20networks/01.%20geometric%20deep%20learning/" class="md-nav__link">
<span class="md-ellipsis">
几何深度学习
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2012%3A%20graph%20neural%20networks/02.%20graph%20theory/" class="md-nav__link">
<span class="md-ellipsis">
图论
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2012%3A%20graph%20neural%20networks/03.%20graph%20neural%20networks/" class="md-nav__link">
<span class="md-ellipsis">
图神经网络
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2012%3A%20graph%20neural%20networks/04.%20graph%20attention%20networks/" class="md-nav__link">
<span class="md-ellipsis">
图注意力网络
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2012%3A%20graph%20neural%20networks/05.%203d%20graph%20networks/" class="md-nav__link">
<span class="md-ellipsis">
3D 图网络
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_14" >
<label class="md-nav__link" for="__nav_14" id="__nav_14_label" tabindex="0">
<span class="md-ellipsis">
计算机与操作系统
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_14_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_14">
<span class="md-nav__icon md-icon"></span>
计算机与操作系统
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2013%3A%20computing%20and%20OS/01.%20discrete%20maths/" class="md-nav__link">
<span class="md-ellipsis">
离散数学
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2013%3A%20computing%20and%20OS/02.%20computer%20architecture/" class="md-nav__link">
<span class="md-ellipsis">
计算机体系结构
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2013%3A%20computing%20and%20OS/03.%20operating%20systems/" class="md-nav__link">
<span class="md-ellipsis">
操作系统
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2013%3A%20computing%20and%20OS/04.%20concurrency%20and%20parallelism/" class="md-nav__link">
<span class="md-ellipsis">
并发与并行
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2013%3A%20computing%20and%20OS/05.%20programming%20languages/" class="md-nav__link">
<span class="md-ellipsis">
编程语言
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--active md-nav__item--section md-nav__item--nested">
<input class="md-nav__toggle md-toggle " type="checkbox" id="__nav_15" checked>
<label class="md-nav__link" for="__nav_15" id="__nav_15_label" tabindex="">
<span class="md-ellipsis">
数据结构与算法
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_15_label" aria-expanded="true">
<label class="md-nav__title" for="__nav_15">
<span class="md-nav__icon md-icon"></span>
数据结构与算法
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../00.%20foundations/" class="md-nav__link">
<span class="md-ellipsis">
基础
</span>
</a>
</li>
<li class="md-nav__item md-nav__item--active">
<input class="md-nav__toggle md-toggle" type="checkbox" id="__toc">
<label class="md-nav__link md-nav__link--active" for="__toc">
<span class="md-ellipsis">
数组与哈希
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<a href="./" class="md-nav__link md-nav__link--active">
<span class="md-ellipsis">
数组与哈希
</span>
</a>
<nav class="md-nav md-nav--secondary" aria-label="目录">
<label class="md-nav__title" for="__toc">
<span class="md-nav__icon md-icon"></span>
目录
</label>
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix>
<li class="md-nav__item">
<a href="#_2" class="md-nav__link">
<span class="md-ellipsis">
数组
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_3" class="md-nav__link">
<span class="md-ellipsis">
字符串
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_4" class="md-nav__link">
<span class="md-ellipsis">
哈希表
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_5" class="md-nav__link">
<span class="md-ellipsis">
模式：哈希表查找
</span>
</a>
<nav class="md-nav" aria-label="模式：哈希表查找">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_6" class="md-nav__link">
<span class="md-ellipsis">
简单：两数之和
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_7" class="md-nav__link">
<span class="md-ellipsis">
中等：字母异位词分组
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_8" class="md-nav__link">
<span class="md-ellipsis">
困难：最长连续序列
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_9" class="md-nav__link">
<span class="md-ellipsis">
模式：双指针
</span>
</a>
<nav class="md-nav" aria-label="模式：双指针">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_10" class="md-nav__link">
<span class="md-ellipsis">
简单：验证回文串
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_11" class="md-nav__link">
<span class="md-ellipsis">
中等：三数之和
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_12" class="md-nav__link">
<span class="md-ellipsis">
困难：接雨水
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_13" class="md-nav__link">
<span class="md-ellipsis">
模式：滑动窗口
</span>
</a>
<nav class="md-nav" aria-label="模式：滑动窗口">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_14" class="md-nav__link">
<span class="md-ellipsis">
简单：买卖股票的最佳时机
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_15" class="md-nav__link">
<span class="md-ellipsis">
中等：无重复字符的最长子串
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_16" class="md-nav__link">
<span class="md-ellipsis">
困难：最小覆盖子串
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_17" class="md-nav__link">
<span class="md-ellipsis">
模式：前缀和
</span>
</a>
<nav class="md-nav" aria-label="模式：前缀和">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_18" class="md-nav__link">
<span class="md-ellipsis">
简单：区间求和查询
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#k" class="md-nav__link">
<span class="md-ellipsis">
中等：和为 K 的子数组
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_19" class="md-nav__link">
<span class="md-ellipsis">
困难：除自身以外数组的乘积
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_20" class="md-nav__link">
<span class="md-ellipsis">
常见陷阱总结
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#neetcode" class="md-nav__link">
<span class="md-ellipsis">
课后练习题（NeetCode）
</span>
</a>
<nav class="md-nav" aria-label="课后练习题（NeetCode）">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_21" class="md-nav__link">
<span class="md-ellipsis">
哈希表查找
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_22" class="md-nav__link">
<span class="md-ellipsis">
双指针
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_23" class="md-nav__link">
<span class="md-ellipsis">
滑动窗口
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_24" class="md-nav__link">
<span class="md-ellipsis">
前缀和
</span>
</a>
</li>
</ul>
</nav>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="../02.%20linked%20lists%2C%20stacks%2C%20and%20queues/" class="md-nav__link">
<span class="md-ellipsis">
链表、栈与队列
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../03.%20trees/" class="md-nav__link">
<span class="md-ellipsis">
树
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../04.%20graphs/" class="md-nav__link">
<span class="md-ellipsis">
图
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../05.%20sorting%20and%20search/" class="md-nav__link">
<span class="md-ellipsis">
排序与搜索
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_16" >
<label class="md-nav__link" for="__nav_16" id="__nav_16_label" tabindex="0">
<span class="md-ellipsis">
生产级软件工程
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_16_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_16">
<span class="md-nav__icon md-icon"></span>
生产级软件工程
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2015%3A%20production%20software%20engineering/01.%20linux%20and%20CMD/" class="md-nav__link">
<span class="md-ellipsis">
Linux 与命令行
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2015%3A%20production%20software%20engineering/02.%20git%20and%20repository%20management/" class="md-nav__link">
<span class="md-ellipsis">
Git 与仓库管理
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2015%3A%20production%20software%20engineering/03.%20codebase%20design/" class="md-nav__link">
<span class="md-ellipsis">
代码设计
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2015%3A%20production%20software%20engineering/04.%20testing%20and%20quality%20assurance/" class="md-nav__link">
<span class="md-ellipsis">
测试与质量保障
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2015%3A%20production%20software%20engineering/05.%20deployment%20and%20devops/" class="md-nav__link">
<span class="md-ellipsis">
部署与 DevOps
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_17" >
<label class="md-nav__link" for="__nav_17" id="__nav_17_label" tabindex="0">
<span class="md-ellipsis">
SIMD 与 GPU 编程
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_17_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_17">
<span class="md-nav__icon md-icon"></span>
SIMD 与 GPU 编程
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/00.%20why%20C%2B%2B%20and%20how%20ML%20frameworks%20work/" class="md-nav__link">
<span class="md-ellipsis">
为什么是 C++ 及 ML 框架原理
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/01.%20hardware%20fundamentals/" class="md-nav__link">
<span class="md-ellipsis">
硬件基础
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/02.%20ARM%20and%20NEON/" class="md-nav__link">
<span class="md-ellipsis">
ARM 与 NEON
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/03.%20x86%20and%20AVX/" class="md-nav__link">
<span class="md-ellipsis">
x86 与 AVX
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/04.%20GPU%20architecture%20and%20CUDA/" class="md-nav__link">
<span class="md-ellipsis">
GPU 架构与 CUDA
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/05.%20triton%2C%20TPUs%20and%20pallax/" class="md-nav__link">
<span class="md-ellipsis">
Triton、TPU 与 Pallas
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/06.%20RISC-V%20and%20embedded%20systems/" class="md-nav__link">
<span class="md-ellipsis">
RISC-V 与嵌入式系统
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2016%3A%20SIMD%20and%20GPU%20programming/07.%20vulkan%20compute%20and%20cross-platform%20GPU/" class="md-nav__link">
<span class="md-ellipsis">
Vulkan Compute 与跨平台 GPU
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_18" >
<label class="md-nav__link" for="__nav_18" id="__nav_18_label" tabindex="0">
<span class="md-ellipsis">
AI 推理
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_18_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_18">
<span class="md-nav__icon md-icon"></span>
AI 推理
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2017%3A%20AI%20inference/01.%20quantisation/" class="md-nav__link">
<span class="md-ellipsis">
量化
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2017%3A%20AI%20inference/02.%20efficient%20architectures/" class="md-nav__link">
<span class="md-ellipsis">
高效架构
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2017%3A%20AI%20inference/03.%20serving%20and%20batching/" class="md-nav__link">
<span class="md-ellipsis">
服务与批处理
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2017%3A%20AI%20inference/04.%20edge%20inference/" class="md-nav__link">
<span class="md-ellipsis">
边缘推理
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2017%3A%20AI%20inference/05.%20scaling%20and%20deployment/" class="md-nav__link">
<span class="md-ellipsis">
扩缩与部署
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_19" >
<label class="md-nav__link" for="__nav_19" id="__nav_19_label" tabindex="0">
<span class="md-ellipsis">
ML 系统设计
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_19_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_19">
<span class="md-nav__icon md-icon"></span>
ML 系统设计
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2018%3A%20ML%20systems%20design/01.%20systems%20design%20fundamentals/" class="md-nav__link">
<span class="md-ellipsis">
系统设计基础
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2018%3A%20ML%20systems%20design/02.%20cloud%20computing/" class="md-nav__link">
<span class="md-ellipsis">
云计算
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2018%3A%20ML%20systems%20design/03.%20large%20scale%20infrastructure/" class="md-nav__link">
<span class="md-ellipsis">
大规模基础设施
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2018%3A%20ML%20systems%20design/04.%20ML%20systems%20design/" class="md-nav__link">
<span class="md-ellipsis">
ML 系统设计
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2018%3A%20ML%20systems%20design/05.%20ML%20design%20examples/" class="md-nav__link">
<span class="md-ellipsis">
ML 设计案例
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_20" >
<label class="md-nav__link" for="__nav_20" id="__nav_20_label" tabindex="0">
<span class="md-ellipsis">
应用 AI
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_20_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_20">
<span class="md-nav__icon md-icon"></span>
应用 AI
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2019%3A%20applied%20AI/01.%20AI%20for%20finance/" class="md-nav__link">
<span class="md-ellipsis">
AI 金融
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2019%3A%20applied%20AI/02.%20protein%20design/" class="md-nav__link">
<span class="md-ellipsis">
蛋白质设计
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2019%3A%20applied%20AI/03.%20drug%20discovery/" class="md-nav__link">
<span class="md-ellipsis">
药物发现
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2019%3A%20applied%20AI/04.%20agentic%20systems/" class="md-nav__link">
<span class="md-ellipsis">
智能体系统
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2019%3A%20applied%20AI/05.%20healthcare/" class="md-nav__link">
<span class="md-ellipsis">
医疗健康
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--nested">
<input class="md-nav__toggle md-toggle md-toggle--indeterminate" type="checkbox" id="__nav_21" >
<label class="md-nav__link" for="__nav_21" id="__nav_21_label" tabindex="0">
<span class="md-ellipsis">
前沿 AI
</span>
<span class="md-nav__icon md-icon"></span>
</label>
<nav class="md-nav" data-md-level="1" aria-labelledby="__nav_21_label" aria-expanded="false">
<label class="md-nav__title" for="__nav_21">
<span class="md-nav__icon md-icon"></span>
前沿 AI
</label>
<ul class="md-nav__list" data-md-scrollfix>
<li class="md-nav__item">
<a href="../../chapter%2020%3A%20bleeding%20edge%20AI/01.%20quantum%20machine%20learning/" class="md-nav__link">
<span class="md-ellipsis">
量子机器学习
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2020%3A%20bleeding%20edge%20AI/02.%20neuromorphic%20computing/" class="md-nav__link">
<span class="md-ellipsis">
神经形态计算
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2020%3A%20bleeding%20edge%20AI/03.%20datacentres%20in%20space/" class="md-nav__link">
<span class="md-ellipsis">
太空数据中心
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2020%3A%20bleeding%20edge%20AI/04.%20decentralised%20AI/" class="md-nav__link">
<span class="md-ellipsis">
去中心化 AI
</span>
</a>
</li>
<li class="md-nav__item">
<a href="../../chapter%2020%3A%20bleeding%20edge%20AI/05.%20brain%20machine%20interfaces/" class="md-nav__link">
<span class="md-ellipsis">
脑机接口
</span>
</a>
</li>
</ul>
</nav>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="md-sidebar md-sidebar--secondary" data-md-component="sidebar" data-md-type="toc" >
<div class="md-sidebar__scrollwrap">
<div class="md-sidebar__inner">
<nav class="md-nav md-nav--secondary" aria-label="目录">
<label class="md-nav__title" for="__toc">
<span class="md-nav__icon md-icon"></span>
目录
</label>
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix>
<li class="md-nav__item">
<a href="#_2" class="md-nav__link">
<span class="md-ellipsis">
数组
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_3" class="md-nav__link">
<span class="md-ellipsis">
字符串
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_4" class="md-nav__link">
<span class="md-ellipsis">
哈希表
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_5" class="md-nav__link">
<span class="md-ellipsis">
模式：哈希表查找
</span>
</a>
<nav class="md-nav" aria-label="模式：哈希表查找">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_6" class="md-nav__link">
<span class="md-ellipsis">
简单：两数之和
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_7" class="md-nav__link">
<span class="md-ellipsis">
中等：字母异位词分组
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_8" class="md-nav__link">
<span class="md-ellipsis">
困难：最长连续序列
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_9" class="md-nav__link">
<span class="md-ellipsis">
模式：双指针
</span>
</a>
<nav class="md-nav" aria-label="模式：双指针">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_10" class="md-nav__link">
<span class="md-ellipsis">
简单：验证回文串
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_11" class="md-nav__link">
<span class="md-ellipsis">
中等：三数之和
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_12" class="md-nav__link">
<span class="md-ellipsis">
困难：接雨水
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_13" class="md-nav__link">
<span class="md-ellipsis">
模式：滑动窗口
</span>
</a>
<nav class="md-nav" aria-label="模式：滑动窗口">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_14" class="md-nav__link">
<span class="md-ellipsis">
简单：买卖股票的最佳时机
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_15" class="md-nav__link">
<span class="md-ellipsis">
中等：无重复字符的最长子串
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_16" class="md-nav__link">
<span class="md-ellipsis">
困难：最小覆盖子串
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_17" class="md-nav__link">
<span class="md-ellipsis">
模式：前缀和
</span>
</a>
<nav class="md-nav" aria-label="模式：前缀和">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_18" class="md-nav__link">
<span class="md-ellipsis">
简单：区间求和查询
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#k" class="md-nav__link">
<span class="md-ellipsis">
中等：和为 K 的子数组
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_19" class="md-nav__link">
<span class="md-ellipsis">
困难：除自身以外数组的乘积
</span>
</a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a href="#_20" class="md-nav__link">
<span class="md-ellipsis">
常见陷阱总结
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#neetcode" class="md-nav__link">
<span class="md-ellipsis">
课后练习题（NeetCode）
</span>
</a>
<nav class="md-nav" aria-label="课后练习题（NeetCode）">
<ul class="md-nav__list">
<li class="md-nav__item">
<a href="#_21" class="md-nav__link">
<span class="md-ellipsis">
哈希表查找
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_22" class="md-nav__link">
<span class="md-ellipsis">
双指针
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_23" class="md-nav__link">
<span class="md-ellipsis">
滑动窗口
</span>
</a>
</li>
<li class="md-nav__item">
<a href="#_24" class="md-nav__link">
<span class="md-ellipsis">
前缀和
</span>
</a>
</li>
</ul>
</nav>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="md-content" data-md-component="content">
<article class="md-content__inner md-typeset">
<h1 id="_1">数组与哈希<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h1>
<p><em>数组和哈希表是编程中最基础的两种数据结构。本文件涵盖它们底层的运行机制，然后构建关键的问题解决模式：双指针、滑动窗口、前缀和以及基于哈希的查找，通过逐步增加难度的题目，并在每一步指出常见陷阱。</em></p>
<ul>
<li>
<p>如果你深入理解数组和哈希表，你可以解决约40%的编码面试题。这两种结构无处不在，因为它们提供了算法最需要的两样东西：<strong>快速索引访问</strong>（数组）和<strong>按键快速查找</strong>（哈希表）。</p>
</li>
<li>
<p>本文件教授的是模式，而非解法。目标是当你看到一个新问题时，你能识别出适用哪个模式以及为什么，而不是试图回忆一个背下来的解法。</p>
</li>
</ul>
<h2 id="_2">数组<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h2>
<ul>
<li>
<p><strong>数组</strong>是一片连续的内存块，元素以固定偏移量存储。访问元素 <span class="arithmatex">\(i\)</span> 的成本是 <span class="arithmatex">\(O(1)\)</span>，因为地址就是 <code>base + i * element_size</code>。这是最快的数据访问方式，也是数组成为默认选择的原因。</p>
</li>
<li>
<p><strong>动态数组</strong>（Python 的 <code>list</code>、Java 的 <code>ArrayList</code>、C++ 的 <code>vector</code>）在满时自动增长。其策略是<strong>平摊加倍</strong>：当数组满时，分配一个两倍大小的新数组并将所有元素复制过去。复制成本为 <span class="arithmatex">\(O(n)\)</span>，但这种情况很少发生（每 <span class="arithmatex">\(n\)</span> 次插入一次），所以每次插入的平摊成本是 <span class="arithmatex">\(O(1)\)</span>。</p>
</li>
<li>
<p><strong>缓存局部性</strong>是数组在实践中很快的原因，而不仅仅是理论上。因为元素是连续存储的，访问一个元素会将其邻近元素加载到 CPU 缓存中（第13章）。遍历数组是缓存友好的；在链表中跟随指针则不是。这个常数因子差异在实际中可能达到 10-100 倍。</p>
</li>
</ul>
<table>
<thead>
<tr>
<th>操作</th>
<th>数组</th>
<th>动态数组</th>
</tr>
</thead>
<tbody>
<tr>
<td>按索引访问</td>
<td><span class="arithmatex">\(O(1)\)</span></td>
<td><span class="arithmatex">\(O(1)\)</span></td>
</tr>
<tr>
<td>追加</td>
<td>不适用</td>
<td><span class="arithmatex">\(O(1)\)</span> 平摊</td>
</tr>
<tr>
<td>在位置 <span class="arithmatex">\(i\)</span> 插入</td>
<td><span class="arithmatex">\(O(n)\)</span></td>
<td><span class="arithmatex">\(O(n)\)</span></td>
</tr>
<tr>
<td>在位置 <span class="arithmatex">\(i\)</span> 删除</td>
<td><span class="arithmatex">\(O(n)\)</span></td>
<td><span class="arithmatex">\(O(n)\)</span></td>
</tr>
<tr>
<td>搜索（未排序）</td>
<td><span class="arithmatex">\(O(n)\)</span></td>
<td><span class="arithmatex">\(O(n)\)</span></td>
</tr>
</tbody>
</table>
<ul>
<li><strong>陷阱</strong>：在数组中间插入或删除是 <span class="arithmatex">\(O(n)\)</span>，因为所有后续元素都必须移动。如果你需要频繁在中间插入，考虑使用链表或其他方法。</li>
</ul>
<h2 id="_3">字符串<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h2>
<ul>
<li><strong>字符串</strong>是一个字符数组。在 Python 中，字符串是不可变的：每次拼接都会创建一个新的字符串。在循环中逐字符构建字符串是 <span class="arithmatex">\(O(n^2)\)</span>，因为每次拼接都会复制到目前为止的整个字符串。</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-0-1" name="__codelineno-0-1" href="#__codelineno-0-1"></a><span class="c1"># 不好：O(n^2) 字符串拼接</span>
<a id="__codelineno-0-2" name="__codelineno-0-2" href="#__codelineno-0-2"></a><span class="n">s</span> <span class="o">=</span> <span class="s2">&quot;&quot;</span>
<a id="__codelineno-0-3" name="__codelineno-0-3" href="#__codelineno-0-3"></a><span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">characters</span><span class="p">:</span>
<a id="__codelineno-0-4" name="__codelineno-0-4" href="#__codelineno-0-4"></a> <span class="n">s</span> <span class="o">+=</span> <span class="n">c</span> <span class="c1"># 每次复制整个字符串</span>
<a id="__codelineno-0-5" name="__codelineno-0-5" href="#__codelineno-0-5"></a>
<a id="__codelineno-0-6" name="__codelineno-0-6" href="#__codelineno-0-6"></a><span class="c1"># 好：O(n) 使用列表然后 join</span>
<a id="__codelineno-0-7" name="__codelineno-0-7" href="#__codelineno-0-7"></a><span class="n">parts</span> <span class="o">=</span> <span class="p">[]</span>
<a id="__codelineno-0-8" name="__codelineno-0-8" href="#__codelineno-0-8"></a><span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">characters</span><span class="p">:</span>
<a id="__codelineno-0-9" name="__codelineno-0-9" href="#__codelineno-0-9"></a> <span class="n">parts</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">c</span><span class="p">)</span>
<a id="__codelineno-0-10" name="__codelineno-0-10" href="#__codelineno-0-10"></a><span class="n">s</span> <span class="o">=</span> <span class="s2">&quot;&quot;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">parts</span><span class="p">)</span>
</code></pre></div>
<ul>
<li>
<p><strong>陷阱</strong>：在 Python 中，循环内的 <code>s += c</code> 是最常见的性能 bug 之一。始终先收集到列表中再 <code>.join()</code>。</p>
</li>
<li>
<p><strong>编码</strong>：ASCII 使用 7 位（128 个字符）。<strong>UTF-8</strong> 是可变长度的：ASCII 字符使用 1 字节，带重音字符使用 2 字节，中文/日文字符使用 3 字节，表情符号使用 4 字节。当问题说"小写英文字母"时，字母表大小为 26，这意味着你可以使用固定大小的数组而不是哈希表。</p>
</li>
</ul>
<h2 id="_4">哈希表<a class="headerlink" href="#_4" title="Permanent link">&para;</a></h2>
<ul>
<li>
<p><strong>哈希表</strong>将键映射到值，平均情况下的查找、插入和删除都是 <span class="arithmatex">\(O(1)\)</span>。它通过计算一个<strong>哈希函数</strong> <span class="arithmatex">\(h(key)\)</span> 将键转换为数组索引来实现。</p>
</li>
<li>
<p>哈希函数必须：<strong>确定性的</strong>（相同键总是得到相同哈希值）、<strong>均匀的</strong>（将键均匀分布到各个桶中）且<strong>计算速度快</strong>。</p>
</li>
<li>
<p><strong>冲突</strong>发生在两个不同的键哈希到相同的索引时。有两种主要策略：</p>
<ul>
<li>
<p><strong>链地址法</strong>：每个桶存储一个键值对链表。发生冲突时，追加到链表。最坏情况（所有键哈希到同一个桶）：<span class="arithmatex">\(O(n)\)</span>。使用好的哈希函数时的平均情况：<span class="arithmatex">\(O(1)\)</span>。</p>
</li>
<li>
<p><strong>开放地址法</strong>：发生冲突时，探测下一个空槽。<strong>线性探测</strong>检查下一个槽位，然后再下一个，以此类推。它缓存友好，但会遭受<strong>聚集</strong>问题（长串的已占用槽位）。<strong>罗宾汉哈希</strong>通过将"离家较近"的条目移位来减少方差。</p>
</li>
</ul>
</li>
<li>
<p><strong>负载因子</strong> <span class="arithmatex">\(\alpha = n / m\)</span>（元素数 / 桶数）决定了性能。当 <span class="arithmatex">\(\alpha\)</span> 超过阈值（通常为 0.75）时，表会<strong>重新哈希</strong>：分配一个更大的表并重新插入所有元素。这需要 <span class="arithmatex">\(O(n)\)</span> 时间，但不常发生。</p>
</li>
<li>
<p><strong>哈希映射</strong>（Python 中的 <code>dict</code>、Java 中的 <code>HashMap</code>）存储键值对。<strong>哈希集合</strong>（Python 中的 <code>set</code>、Java 中的 <code>HashSet</code>）只存储键（用于快速成员测试）。</p>
</li>
</ul>
<table>
<thead>
<tr>
<th>操作</th>
<th>平均</th>
<th>最坏情况</th>
</tr>
</thead>
<tbody>
<tr>
<td>查找</td>
<td><span class="arithmatex">\(O(1)\)</span></td>
<td><span class="arithmatex">\(O(n)\)</span></td>
</tr>
<tr>
<td>插入</td>
<td><span class="arithmatex">\(O(1)\)</span></td>
<td><span class="arithmatex">\(O(n)\)</span></td>
</tr>
<tr>
<td>删除</td>
<td><span class="arithmatex">\(O(1)\)</span></td>
<td><span class="arithmatex">\(O(n)\)</span></td>
</tr>
</tbody>
</table>
<ul>
<li>
<p><strong>布隆过滤器</strong>是空间高效的概率性集合。它可以告诉你"肯定不在集合中"或"可能在集合中"（具有可调的假阳性率）。它使用 <span class="arithmatex">\(k\)</span> 个哈希函数和一个位数组。用于数据库（避免对不存在的键进行磁盘读取）、Web 缓存和拼写检查器。</p>
</li>
<li>
<p><strong>何时使用哈希表</strong>：每当你需要用 <span class="arithmatex">\(O(1)\)</span> 的时间回答"我之前见过这个吗？"或"与这个键关联的计数/索引/值是什么？"时。如果你正在反复进行线性扫描寻找某物，哈希表几乎总能使其更快。</p>
</li>
</ul>
<hr />
<h2 id="_5">模式：哈希表查找<a class="headerlink" href="#_5" title="Permanent link">&para;</a></h2>
<ul>
<li>最基本的模式：使用哈希表将 <span class="arithmatex">\(O(n)\)</span> 扫描替换为 <span class="arithmatex">\(O(1)\)</span> 查找。</li>
</ul>
<h3 id="_6">简单：两数之和<a class="headerlink" href="#_6" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定一个整数数组和一个目标值，返回两个数的索引，使它们的和等于目标值。</p>
</li>
<li>
<p><strong>暴力解法</strong> <span class="arithmatex">\(O(n^2)\)</span>：检查每一对。</p>
</li>
<li>
<p><strong>模式洞察</strong>：对于每个数字 <code>num</code>，需要 <code>target - num</code> 存在于数组中的某处。与其扫描数组寻找它，不如将之前见过的数字存储在一个哈希表中。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-1-1" name="__codelineno-1-1" href="#__codelineno-1-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">two_sum</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">target</span><span class="p">):</span>
<a id="__codelineno-1-2" name="__codelineno-1-2" href="#__codelineno-1-2"></a> <span class="n">seen</span> <span class="o">=</span> <span class="p">{}</span> <span class="c1"># 值 -&gt; 索引</span>
<a id="__codelineno-1-3" name="__codelineno-1-3" href="#__codelineno-1-3"></a> <span class="k">for</span> <span class="n">i</span><span class="p">,</span> <span class="n">num</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">nums</span><span class="p">):</span>
<a id="__codelineno-1-4" name="__codelineno-1-4" href="#__codelineno-1-4"></a> <span class="n">complement</span> <span class="o">=</span> <span class="n">target</span> <span class="o">-</span> <span class="n">num</span>
<a id="__codelineno-1-5" name="__codelineno-1-5" href="#__codelineno-1-5"></a> <span class="k">if</span> <span class="n">complement</span> <span class="ow">in</span> <span class="n">seen</span><span class="p">:</span>
<a id="__codelineno-1-6" name="__codelineno-1-6" href="#__codelineno-1-6"></a> <span class="k">return</span> <span class="p">[</span><span class="n">seen</span><span class="p">[</span><span class="n">complement</span><span class="p">],</span> <span class="n">i</span><span class="p">]</span>
<a id="__codelineno-1-7" name="__codelineno-1-7" href="#__codelineno-1-7"></a> <span class="n">seen</span><span class="p">[</span><span class="n">num</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span>
</code></pre></div>
<ul>
<li>
<p><strong>为什么有效</strong>：一次遍历数组。对于每个元素，哈希表查找是 <span class="arithmatex">\(O(1)\)</span>。总计：<span class="arithmatex">\(O(n)\)</span> 时间，<span class="arithmatex">\(O(n)\)</span> 空间。</p>
</li>
<li>
<p><strong>陷阱</strong>：在检查补数之前不要将当前数字添加到哈希表，否则可能会让元素与自身匹配。上面代码中的顺序是正确的：先检查，后插入。</p>
</li>
</ul>
<h3 id="_7">中等：字母异位词分组<a class="headerlink" href="#_7" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定一个字符串列表，将字母异位词分组在一起。（"eat"、"tea"、"ate"）是一组。</p>
</li>
<li>
<p><strong>模式洞察</strong>：异位词具有相同的字符但顺序不同。如果对每个字符串进行排序，异位词会产生相同的排序后键。使用这个排序后的键作为哈希表的键。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-2-1" name="__codelineno-2-1" href="#__codelineno-2-1"></a><span class="kn">from</span><span class="w"> </span><span class="nn">collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">defaultdict</span>
<a id="__codelineno-2-2" name="__codelineno-2-2" href="#__codelineno-2-2"></a>
<a id="__codelineno-2-3" name="__codelineno-2-3" href="#__codelineno-2-3"></a><span class="k">def</span><span class="w"> </span><span class="nf">group_anagrams</span><span class="p">(</span><span class="n">strs</span><span class="p">):</span>
<a id="__codelineno-2-4" name="__codelineno-2-4" href="#__codelineno-2-4"></a> <span class="n">groups</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">list</span><span class="p">)</span>
<a id="__codelineno-2-5" name="__codelineno-2-5" href="#__codelineno-2-5"></a> <span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="n">strs</span><span class="p">:</span>
<a id="__codelineno-2-6" name="__codelineno-2-6" href="#__codelineno-2-6"></a> <span class="n">key</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">(</span><span class="nb">sorted</span><span class="p">(</span><span class="n">s</span><span class="p">))</span> <span class="c1"># 或使用字符计数元组</span>
<a id="__codelineno-2-7" name="__codelineno-2-7" href="#__codelineno-2-7"></a> <span class="n">groups</span><span class="p">[</span><span class="n">key</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">s</span><span class="p">)</span>
<a id="__codelineno-2-8" name="__codelineno-2-8" href="#__codelineno-2-8"></a> <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="n">groups</span><span class="o">.</span><span class="n">values</span><span class="p">())</span>
</code></pre></div>
<ul>
<li><strong>优化</strong>：对每个字符串排序需要 <span class="arithmatex">\(O(k \log k)\)</span>，其中 <span class="arithmatex">\(k\)</span> 是字符串长度。为了更快的键，统计字符频率并使用计数元组作为键：</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-3-1" name="__codelineno-3-1" href="#__codelineno-3-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">group_anagrams_fast</span><span class="p">(</span><span class="n">strs</span><span class="p">):</span>
<a id="__codelineno-3-2" name="__codelineno-3-2" href="#__codelineno-3-2"></a> <span class="n">groups</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">list</span><span class="p">)</span>
<a id="__codelineno-3-3" name="__codelineno-3-3" href="#__codelineno-3-3"></a> <span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="n">strs</span><span class="p">:</span>
<a id="__codelineno-3-4" name="__codelineno-3-4" href="#__codelineno-3-4"></a> <span class="n">count</span> <span class="o">=</span> <span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">*</span> <span class="mi">26</span>
<a id="__codelineno-3-5" name="__codelineno-3-5" href="#__codelineno-3-5"></a> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">s</span><span class="p">:</span>
<a id="__codelineno-3-6" name="__codelineno-3-6" href="#__codelineno-3-6"></a> <span class="n">count</span><span class="p">[</span><span class="nb">ord</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> <span class="o">-</span> <span class="nb">ord</span><span class="p">(</span><span class="s1">&#39;a&#39;</span><span class="p">)]</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-3-7" name="__codelineno-3-7" href="#__codelineno-3-7"></a> <span class="n">groups</span><span class="p">[</span><span class="nb">tuple</span><span class="p">(</span><span class="n">count</span><span class="p">)]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">s</span><span class="p">)</span>
<a id="__codelineno-3-8" name="__codelineno-3-8" href="#__codelineno-3-8"></a> <span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="n">groups</span><span class="o">.</span><span class="n">values</span><span class="p">())</span>
</code></pre></div>
<ul>
<li>
<p>这样每个字符串是 <span class="arithmatex">\(O(k)\)</span> 而不是 <span class="arithmatex">\(O(k \log k)\)</span>。字符计数元组是一种<strong>规范形式</strong>：对组内所有成员都相同的表示。</p>
</li>
<li>
<p><strong>陷阱</strong>：在 Python 中，列表不可哈希（不能用作字典键）。你必须转换为元组。当人们尝试 <code>groups[count].append(s)</code> 时就会出错。</p>
</li>
</ul>
<h3 id="_8">困难：最长连续序列<a class="headerlink" href="#_8" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定一个未排序的数组，找出最长连续序列的长度（例如，[100, 4, 200, 1, 3, 2] → 4，因为 [1, 2, 3, 4]）。</p>
</li>
<li>
<p><strong>暴力解法</strong> <span class="arithmatex">\(O(n \log n)\)</span>：对数组排序，然后扫描连续段。</p>
</li>
<li>
<p><strong>模式洞察</strong>：将所有数字放入哈希集以实现 <span class="arithmatex">\(O(1)\)</span> 查找。对于每个数字，检查它是否是一个序列的<strong>起点</strong>（即 <code>num - 1</code> 不在集合中）。如果是，则计算该序列能延伸多远。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-4-1" name="__codelineno-4-1" href="#__codelineno-4-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">longest_consecutive</span><span class="p">(</span><span class="n">nums</span><span class="p">):</span>
<a id="__codelineno-4-2" name="__codelineno-4-2" href="#__codelineno-4-2"></a> <span class="n">num_set</span> <span class="o">=</span> <span class="nb">set</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span>
<a id="__codelineno-4-3" name="__codelineno-4-3" href="#__codelineno-4-3"></a> <span class="n">best</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-4-4" name="__codelineno-4-4" href="#__codelineno-4-4"></a>
<a id="__codelineno-4-5" name="__codelineno-4-5" href="#__codelineno-4-5"></a> <span class="k">for</span> <span class="n">num</span> <span class="ow">in</span> <span class="n">num_set</span><span class="p">:</span>
<a id="__codelineno-4-6" name="__codelineno-4-6" href="#__codelineno-4-6"></a> <span class="c1"># 只从序列的开头开始计数</span>
<a id="__codelineno-4-7" name="__codelineno-4-7" href="#__codelineno-4-7"></a> <span class="k">if</span> <span class="n">num</span> <span class="o">-</span> <span class="mi">1</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">num_set</span><span class="p">:</span>
<a id="__codelineno-4-8" name="__codelineno-4-8" href="#__codelineno-4-8"></a> <span class="n">length</span> <span class="o">=</span> <span class="mi">1</span>
<a id="__codelineno-4-9" name="__codelineno-4-9" href="#__codelineno-4-9"></a> <span class="k">while</span> <span class="n">num</span> <span class="o">+</span> <span class="n">length</span> <span class="ow">in</span> <span class="n">num_set</span><span class="p">:</span>
<a id="__codelineno-4-10" name="__codelineno-4-10" href="#__codelineno-4-10"></a> <span class="n">length</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-4-11" name="__codelineno-4-11" href="#__codelineno-4-11"></a> <span class="n">best</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">best</span><span class="p">,</span> <span class="n">length</span><span class="p">)</span>
<a id="__codelineno-4-12" name="__codelineno-4-12" href="#__codelineno-4-12"></a>
<a id="__codelineno-4-13" name="__codelineno-4-13" href="#__codelineno-4-13"></a> <span class="k">return</span> <span class="n">best</span>
</code></pre></div>
<ul>
<li>
<p><strong>为什么是 <span class="arithmatex">\(O(n)\)</span></strong>：内部 <code>while</code> 循环在所有迭代中总共最多运行 <span class="arithmatex">\(n\)</span> 次（每个数字最多被访问两次：一次在外层循环，一次在 <code>while</code> 扩展中）。<code>if num - 1 not in num_set</code> 守卫确保我们只从序列起点开始计数。</p>
</li>
<li>
<p><strong>陷阱</strong>：如果没有 <code>if num - 1 not in num_set</code> 检查，你会从每个元素开始计数，在最坏情况下会变成 <span class="arithmatex">\(O(n^2)\)</span>（例如，[1, 2, 3, ..., n] 会从每个起点扫描整个序列）。</p>
</li>
</ul>
<hr />
<h2 id="_9">模式：双指针<a class="headerlink" href="#_9" title="Permanent link">&para;</a></h2>
<ul>
<li>
<p><strong>双指针</strong>模式使用两个索引在数组中移动，通常从两端向中间或从同端以不同速度移动。它在数组已排序或需要比较成对元素时有效。</p>
</li>
<li>
<p><strong>何时使用</strong>：问题涉及成对、子数组或分区，并且数组已排序（或可在不丢失所需信息的情况下排序）。</p>
</li>
</ul>
<h3 id="_10">简单：验证回文串<a class="headerlink" href="#_10" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：判断一个字符串是否是回文串，只考虑字母数字字符并忽略大小写。</p>
</li>
<li>
<p><strong>模式</strong>：一个指针在开头，一个在结尾。向中间移动，比较字符。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-5-1" name="__codelineno-5-1" href="#__codelineno-5-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">is_palindrome</span><span class="p">(</span><span class="n">s</span><span class="p">):</span>
<a id="__codelineno-5-2" name="__codelineno-5-2" href="#__codelineno-5-2"></a> <span class="n">left</span><span class="p">,</span> <span class="n">right</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">s</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
<a id="__codelineno-5-3" name="__codelineno-5-3" href="#__codelineno-5-3"></a>
<a id="__codelineno-5-4" name="__codelineno-5-4" href="#__codelineno-5-4"></a> <span class="k">while</span> <span class="n">left</span> <span class="o">&lt;</span> <span class="n">right</span><span class="p">:</span>
<a id="__codelineno-5-5" name="__codelineno-5-5" href="#__codelineno-5-5"></a> <span class="c1"># 跳过非字母数字字符</span>
<a id="__codelineno-5-6" name="__codelineno-5-6" href="#__codelineno-5-6"></a> <span class="k">while</span> <span class="n">left</span> <span class="o">&lt;</span> <span class="n">right</span> <span class="ow">and</span> <span class="ow">not</span> <span class="n">s</span><span class="p">[</span><span class="n">left</span><span class="p">]</span><span class="o">.</span><span class="n">isalnum</span><span class="p">():</span>
<a id="__codelineno-5-7" name="__codelineno-5-7" href="#__codelineno-5-7"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-5-8" name="__codelineno-5-8" href="#__codelineno-5-8"></a> <span class="k">while</span> <span class="n">left</span> <span class="o">&lt;</span> <span class="n">right</span> <span class="ow">and</span> <span class="ow">not</span> <span class="n">s</span><span class="p">[</span><span class="n">right</span><span class="p">]</span><span class="o">.</span><span class="n">isalnum</span><span class="p">():</span>
<a id="__codelineno-5-9" name="__codelineno-5-9" href="#__codelineno-5-9"></a> <span class="n">right</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-5-10" name="__codelineno-5-10" href="#__codelineno-5-10"></a>
<a id="__codelineno-5-11" name="__codelineno-5-11" href="#__codelineno-5-11"></a> <span class="k">if</span> <span class="n">s</span><span class="p">[</span><span class="n">left</span><span class="p">]</span><span class="o">.</span><span class="n">lower</span><span class="p">()</span> <span class="o">!=</span> <span class="n">s</span><span class="p">[</span><span class="n">right</span><span class="p">]</span><span class="o">.</span><span class="n">lower</span><span class="p">():</span>
<a id="__codelineno-5-12" name="__codelineno-5-12" href="#__codelineno-5-12"></a> <span class="k">return</span> <span class="kc">False</span>
<a id="__codelineno-5-13" name="__codelineno-5-13" href="#__codelineno-5-13"></a>
<a id="__codelineno-5-14" name="__codelineno-5-14" href="#__codelineno-5-14"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-5-15" name="__codelineno-5-15" href="#__codelineno-5-15"></a> <span class="n">right</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-5-16" name="__codelineno-5-16" href="#__codelineno-5-16"></a>
<a id="__codelineno-5-17" name="__codelineno-5-17" href="#__codelineno-5-17"></a> <span class="k">return</span> <span class="kc">True</span>
</code></pre></div>
<ul>
<li><strong>陷阱</strong>：忘记内部 while 循环中的 <code>left &lt; right</code> 检查。没有它，在像 "!!!"（全部非字母数字）这样的字符串上指针可能越界。</li>
</ul>
<h3 id="_11">中等：三数之和<a class="headerlink" href="#_11" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：找出数组中所有唯一的三元组，使其和为零。</p>
</li>
<li>
<p><strong>模式</strong>：对数组排序。固定一个元素，然后在剩余部分使用双指针找到和为固定元素相反数的对。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-6-1" name="__codelineno-6-1" href="#__codelineno-6-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">three_sum</span><span class="p">(</span><span class="n">nums</span><span class="p">):</span>
<a id="__codelineno-6-2" name="__codelineno-6-2" href="#__codelineno-6-2"></a> <span class="n">nums</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span>
<a id="__codelineno-6-3" name="__codelineno-6-3" href="#__codelineno-6-3"></a> <span class="n">result</span> <span class="o">=</span> <span class="p">[]</span>
<a id="__codelineno-6-4" name="__codelineno-6-4" href="#__codelineno-6-4"></a>
<a id="__codelineno-6-5" name="__codelineno-6-5" href="#__codelineno-6-5"></a> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span> <span class="o">-</span> <span class="mi">2</span><span class="p">):</span>
<a id="__codelineno-6-6" name="__codelineno-6-6" href="#__codelineno-6-6"></a> <span class="c1"># 跳过重复的固定元素</span>
<a id="__codelineno-6-7" name="__codelineno-6-7" href="#__codelineno-6-7"></a> <span class="k">if</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="mi">0</span> <span class="ow">and</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]:</span>
<a id="__codelineno-6-8" name="__codelineno-6-8" href="#__codelineno-6-8"></a> <span class="k">continue</span>
<a id="__codelineno-6-9" name="__codelineno-6-9" href="#__codelineno-6-9"></a>
<a id="__codelineno-6-10" name="__codelineno-6-10" href="#__codelineno-6-10"></a> <span class="n">left</span><span class="p">,</span> <span class="n">right</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
<a id="__codelineno-6-11" name="__codelineno-6-11" href="#__codelineno-6-11"></a> <span class="n">target</span> <span class="o">=</span> <span class="o">-</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<a id="__codelineno-6-12" name="__codelineno-6-12" href="#__codelineno-6-12"></a>
<a id="__codelineno-6-13" name="__codelineno-6-13" href="#__codelineno-6-13"></a> <span class="k">while</span> <span class="n">left</span> <span class="o">&lt;</span> <span class="n">right</span><span class="p">:</span>
<a id="__codelineno-6-14" name="__codelineno-6-14" href="#__codelineno-6-14"></a> <span class="n">total</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="n">left</span><span class="p">]</span> <span class="o">+</span> <span class="n">nums</span><span class="p">[</span><span class="n">right</span><span class="p">]</span>
<a id="__codelineno-6-15" name="__codelineno-6-15" href="#__codelineno-6-15"></a> <span class="k">if</span> <span class="n">total</span> <span class="o">&lt;</span> <span class="n">target</span><span class="p">:</span>
<a id="__codelineno-6-16" name="__codelineno-6-16" href="#__codelineno-6-16"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-6-17" name="__codelineno-6-17" href="#__codelineno-6-17"></a> <span class="k">elif</span> <span class="n">total</span> <span class="o">&gt;</span> <span class="n">target</span><span class="p">:</span>
<a id="__codelineno-6-18" name="__codelineno-6-18" href="#__codelineno-6-18"></a> <span class="n">right</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-6-19" name="__codelineno-6-19" href="#__codelineno-6-19"></a> <span class="k">else</span><span class="p">:</span>
<a id="__codelineno-6-20" name="__codelineno-6-20" href="#__codelineno-6-20"></a> <span class="n">result</span><span class="o">.</span><span class="n">append</span><span class="p">([</span><span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">left</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">right</span><span class="p">]])</span>
<a id="__codelineno-6-21" name="__codelineno-6-21" href="#__codelineno-6-21"></a> <span class="c1"># 跳过重复项</span>
<a id="__codelineno-6-22" name="__codelineno-6-22" href="#__codelineno-6-22"></a> <span class="k">while</span> <span class="n">left</span> <span class="o">&lt;</span> <span class="n">right</span> <span class="ow">and</span> <span class="n">nums</span><span class="p">[</span><span class="n">left</span><span class="p">]</span> <span class="o">==</span> <span class="n">nums</span><span class="p">[</span><span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]:</span>
<a id="__codelineno-6-23" name="__codelineno-6-23" href="#__codelineno-6-23"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-6-24" name="__codelineno-6-24" href="#__codelineno-6-24"></a> <span class="k">while</span> <span class="n">left</span> <span class="o">&lt;</span> <span class="n">right</span> <span class="ow">and</span> <span class="n">nums</span><span class="p">[</span><span class="n">right</span><span class="p">]</span> <span class="o">==</span> <span class="n">nums</span><span class="p">[</span><span class="n">right</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]:</span>
<a id="__codelineno-6-25" name="__codelineno-6-25" href="#__codelineno-6-25"></a> <span class="n">right</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-6-26" name="__codelineno-6-26" href="#__codelineno-6-26"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-6-27" name="__codelineno-6-27" href="#__codelineno-6-27"></a> <span class="n">right</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-6-28" name="__codelineno-6-28" href="#__codelineno-6-28"></a>
<a id="__codelineno-6-29" name="__codelineno-6-29" href="#__codelineno-6-29"></a> <span class="k">return</span> <span class="n">result</span>
</code></pre></div>
<ul>
<li>
<p><strong>为什么有效</strong>：排序是 <span class="arithmatex">\(O(n \log n)\)</span>。对于每个固定元素，双指针扫描是 <span class="arithmatex">\(O(n)\)</span>。总计：<span class="arithmatex">\(O(n^2)\)</span>，这是该问题的最优解（你必须考虑所有成对组合）。</p>
</li>
<li>
<p><strong>陷阱</strong>：处理重复项是最难的部分。没有跳过重复的逻辑（对固定元素和双指针结果都是如此），你会返回重复的三元组。<code>if i &gt; 0 and nums[i] == nums[i-1]: continue</code> 这行至关重要。</p>
</li>
</ul>
<h3 id="_12">困难：接雨水<a class="headerlink" href="#_12" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定一个高度图（非负整数数组），计算下雨后它能接住多少水。</p>
</li>
<li>
<p><strong>模式洞察</strong>：对于每个位置，水位由它左边最大高度和右边最大高度中的最小值减去当前高度决定。从两端开始的双指针跟踪这些运行中的最大值。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-7-1" name="__codelineno-7-1" href="#__codelineno-7-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">trap</span><span class="p">(</span><span class="n">height</span><span class="p">):</span>
<a id="__codelineno-7-2" name="__codelineno-7-2" href="#__codelineno-7-2"></a> <span class="n">left</span><span class="p">,</span> <span class="n">right</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">height</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
<a id="__codelineno-7-3" name="__codelineno-7-3" href="#__codelineno-7-3"></a> <span class="n">left_max</span><span class="p">,</span> <span class="n">right_max</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
<a id="__codelineno-7-4" name="__codelineno-7-4" href="#__codelineno-7-4"></a> <span class="n">water</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-7-5" name="__codelineno-7-5" href="#__codelineno-7-5"></a>
<a id="__codelineno-7-6" name="__codelineno-7-6" href="#__codelineno-7-6"></a> <span class="k">while</span> <span class="n">left</span> <span class="o">&lt;</span> <span class="n">right</span><span class="p">:</span>
<a id="__codelineno-7-7" name="__codelineno-7-7" href="#__codelineno-7-7"></a> <span class="k">if</span> <span class="n">height</span><span class="p">[</span><span class="n">left</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">height</span><span class="p">[</span><span class="n">right</span><span class="p">]:</span>
<a id="__codelineno-7-8" name="__codelineno-7-8" href="#__codelineno-7-8"></a> <span class="k">if</span> <span class="n">height</span><span class="p">[</span><span class="n">left</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">left_max</span><span class="p">:</span>
<a id="__codelineno-7-9" name="__codelineno-7-9" href="#__codelineno-7-9"></a> <span class="n">left_max</span> <span class="o">=</span> <span class="n">height</span><span class="p">[</span><span class="n">left</span><span class="p">]</span>
<a id="__codelineno-7-10" name="__codelineno-7-10" href="#__codelineno-7-10"></a> <span class="k">else</span><span class="p">:</span>
<a id="__codelineno-7-11" name="__codelineno-7-11" href="#__codelineno-7-11"></a> <span class="n">water</span> <span class="o">+=</span> <span class="n">left_max</span> <span class="o">-</span> <span class="n">height</span><span class="p">[</span><span class="n">left</span><span class="p">]</span>
<a id="__codelineno-7-12" name="__codelineno-7-12" href="#__codelineno-7-12"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-7-13" name="__codelineno-7-13" href="#__codelineno-7-13"></a> <span class="k">else</span><span class="p">:</span>
<a id="__codelineno-7-14" name="__codelineno-7-14" href="#__codelineno-7-14"></a> <span class="k">if</span> <span class="n">height</span><span class="p">[</span><span class="n">right</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">right_max</span><span class="p">:</span>
<a id="__codelineno-7-15" name="__codelineno-7-15" href="#__codelineno-7-15"></a> <span class="n">right_max</span> <span class="o">=</span> <span class="n">height</span><span class="p">[</span><span class="n">right</span><span class="p">]</span>
<a id="__codelineno-7-16" name="__codelineno-7-16" href="#__codelineno-7-16"></a> <span class="k">else</span><span class="p">:</span>
<a id="__codelineno-7-17" name="__codelineno-7-17" href="#__codelineno-7-17"></a> <span class="n">water</span> <span class="o">+=</span> <span class="n">right_max</span> <span class="o">-</span> <span class="n">height</span><span class="p">[</span><span class="n">right</span><span class="p">]</span>
<a id="__codelineno-7-18" name="__codelineno-7-18" href="#__codelineno-7-18"></a> <span class="n">right</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-7-19" name="__codelineno-7-19" href="#__codelineno-7-19"></a>
<a id="__codelineno-7-20" name="__codelineno-7-20" href="#__codelineno-7-20"></a> <span class="k">return</span> <span class="n">water</span>
</code></pre></div>
<ul>
<li>
<p><strong>为什么有效</strong>：关键的洞察是，如果 <code>height[left] &lt; height[right]</code>，那么位置 <code>left</code> 处的水由 <code>left_max</code> 限制（我们知道右边有更高的柱子，所以右边不可能是瓶颈）。我们处理较短的一侧，保证另一侧有更高的柱子。</p>
</li>
<li>
<p><strong>陷阱</strong>：很多人试图先预计算 <code>left_max[i]</code> 和 <code>right_max[i]</code> 数组（这可行但使用 <span class="arithmatex">\(O(n)\)</span> 空间）。双指针方法实现了 <span class="arithmatex">\(O(1)\)</span> 空间。另外，在最大值更新中混淆 <code>&gt;=</code> 和 <code>&gt;</code> 会导致差一错误的水量计算。</p>
</li>
</ul>
<hr />
<h2 id="_13">模式：滑动窗口<a class="headerlink" href="#_13" title="Permanent link">&para;</a></h2>
<ul>
<li>
<p><strong>滑动窗口</strong>模式维护一个窗口（连续子数组），随着迭代扩展和收缩。它适用于询问满足某个条件的子数组或子串的问题。</p>
</li>
<li>
<p><strong>何时使用</strong>：问题要求满足约束条件的最长/最短子数组或子串，且扩展/收缩窗口是单调的（添加元素只能使约束更难/更容易满足，而不是两者兼有）。</p>
</li>
<li>
<p><strong>模板</strong>：</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-8-1" name="__codelineno-8-1" href="#__codelineno-8-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">sliding_window</span><span class="p">(</span><span class="n">arr</span><span class="p">):</span>
<a id="__codelineno-8-2" name="__codelineno-8-2" href="#__codelineno-8-2"></a> <span class="n">left</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-8-3" name="__codelineno-8-3" href="#__codelineno-8-3"></a> <span class="n">state</span> <span class="o">=</span> <span class="o">...</span> <span class="c1"># 窗口状态（计数、和等）</span>
<a id="__codelineno-8-4" name="__codelineno-8-4" href="#__codelineno-8-4"></a> <span class="n">best</span> <span class="o">=</span> <span class="o">...</span>
<a id="__codelineno-8-5" name="__codelineno-8-5" href="#__codelineno-8-5"></a>
<a id="__codelineno-8-6" name="__codelineno-8-6" href="#__codelineno-8-6"></a> <span class="k">for</span> <span class="n">right</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">arr</span><span class="p">)):</span>
<a id="__codelineno-8-7" name="__codelineno-8-7" href="#__codelineno-8-7"></a> <span class="c1"># 扩展：将 arr[right] 添加到窗口状态</span>
<a id="__codelineno-8-8" name="__codelineno-8-8" href="#__codelineno-8-8"></a> <span class="n">update_state</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="n">arr</span><span class="p">[</span><span class="n">right</span><span class="p">])</span>
<a id="__codelineno-8-9" name="__codelineno-8-9" href="#__codelineno-8-9"></a>
<a id="__codelineno-8-10" name="__codelineno-8-10" href="#__codelineno-8-10"></a> <span class="c1"># 收缩：当约束被违反时从左侧缩小</span>
<a id="__codelineno-8-11" name="__codelineno-8-11" href="#__codelineno-8-11"></a> <span class="k">while</span> <span class="n">constraint_violated</span><span class="p">(</span><span class="n">state</span><span class="p">):</span>
<a id="__codelineno-8-12" name="__codelineno-8-12" href="#__codelineno-8-12"></a> <span class="n">remove_from_state</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="n">arr</span><span class="p">[</span><span class="n">left</span><span class="p">])</span>
<a id="__codelineno-8-13" name="__codelineno-8-13" href="#__codelineno-8-13"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-8-14" name="__codelineno-8-14" href="#__codelineno-8-14"></a>
<a id="__codelineno-8-15" name="__codelineno-8-15" href="#__codelineno-8-15"></a> <span class="c1"># 更新答案</span>
<a id="__codelineno-8-16" name="__codelineno-8-16" href="#__codelineno-8-16"></a> <span class="n">best</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">best</span><span class="p">,</span> <span class="n">right</span> <span class="o">-</span> <span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="c1"># 或 min，取决于问题</span>
<a id="__codelineno-8-17" name="__codelineno-8-17" href="#__codelineno-8-17"></a>
<a id="__codelineno-8-18" name="__codelineno-8-18" href="#__codelineno-8-18"></a> <span class="k">return</span> <span class="n">best</span>
</code></pre></div>
<h3 id="_14">简单：买卖股票的最佳时机<a class="headerlink" href="#_14" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定每日价格，找出一笔交易（先买后卖）的最大利润。</p>
</li>
<li>
<p><strong>模式</strong>：跟踪到目前为止的最小价格（窗口的左边界），并在每一天计算利润。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-9-1" name="__codelineno-9-1" href="#__codelineno-9-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">max_profit</span><span class="p">(</span><span class="n">prices</span><span class="p">):</span>
<a id="__codelineno-9-2" name="__codelineno-9-2" href="#__codelineno-9-2"></a> <span class="n">min_price</span> <span class="o">=</span> <span class="nb">float</span><span class="p">(</span><span class="s1">&#39;inf&#39;</span><span class="p">)</span>
<a id="__codelineno-9-3" name="__codelineno-9-3" href="#__codelineno-9-3"></a> <span class="n">max_profit</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-9-4" name="__codelineno-9-4" href="#__codelineno-9-4"></a>
<a id="__codelineno-9-5" name="__codelineno-9-5" href="#__codelineno-9-5"></a> <span class="k">for</span> <span class="n">price</span> <span class="ow">in</span> <span class="n">prices</span><span class="p">:</span>
<a id="__codelineno-9-6" name="__codelineno-9-6" href="#__codelineno-9-6"></a> <span class="n">min_price</span> <span class="o">=</span> <span class="nb">min</span><span class="p">(</span><span class="n">min_price</span><span class="p">,</span> <span class="n">price</span><span class="p">)</span>
<a id="__codelineno-9-7" name="__codelineno-9-7" href="#__codelineno-9-7"></a> <span class="n">max_profit</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">max_profit</span><span class="p">,</span> <span class="n">price</span> <span class="o">-</span> <span class="n">min_price</span><span class="p">)</span>
<a id="__codelineno-9-8" name="__codelineno-9-8" href="#__codelineno-9-8"></a>
<a id="__codelineno-9-9" name="__codelineno-9-9" href="#__codelineno-9-9"></a> <span class="k">return</span> <span class="n">max_profit</span>
</code></pre></div>
<ul>
<li>这是一个退化的滑动窗口：左指针（最低价格）只在找到新最小值时向前移动。<span class="arithmatex">\(O(n)\)</span> 时间，<span class="arithmatex">\(O(1)\)</span> 空间。</li>
</ul>
<h3 id="_15">中等：无重复字符的最长子串<a class="headerlink" href="#_15" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：找出不含重复字符的最长子串的长度。</p>
</li>
<li>
<p><strong>模式</strong>：通过移动 <code>right</code> 扩展窗口。当发现重复时，从左侧收缩直到重复被移除。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-10-1" name="__codelineno-10-1" href="#__codelineno-10-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">length_of_longest_substring</span><span class="p">(</span><span class="n">s</span><span class="p">):</span>
<a id="__codelineno-10-2" name="__codelineno-10-2" href="#__codelineno-10-2"></a> <span class="n">char_index</span> <span class="o">=</span> <span class="p">{}</span> <span class="c1"># 字符 -&gt; 它的最近索引</span>
<a id="__codelineno-10-3" name="__codelineno-10-3" href="#__codelineno-10-3"></a> <span class="n">left</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-10-4" name="__codelineno-10-4" href="#__codelineno-10-4"></a> <span class="n">best</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-10-5" name="__codelineno-10-5" href="#__codelineno-10-5"></a>
<a id="__codelineno-10-6" name="__codelineno-10-6" href="#__codelineno-10-6"></a> <span class="k">for</span> <span class="n">right</span><span class="p">,</span> <span class="n">char</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">s</span><span class="p">):</span>
<a id="__codelineno-10-7" name="__codelineno-10-7" href="#__codelineno-10-7"></a> <span class="k">if</span> <span class="n">char</span> <span class="ow">in</span> <span class="n">char_index</span> <span class="ow">and</span> <span class="n">char_index</span><span class="p">[</span><span class="n">char</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">left</span><span class="p">:</span>
<a id="__codelineno-10-8" name="__codelineno-10-8" href="#__codelineno-10-8"></a> <span class="n">left</span> <span class="o">=</span> <span class="n">char_index</span><span class="p">[</span><span class="n">char</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span> <span class="c1"># 跳过重复字符</span>
<a id="__codelineno-10-9" name="__codelineno-10-9" href="#__codelineno-10-9"></a>
<a id="__codelineno-10-10" name="__codelineno-10-10" href="#__codelineno-10-10"></a> <span class="n">char_index</span><span class="p">[</span><span class="n">char</span><span class="p">]</span> <span class="o">=</span> <span class="n">right</span>
<a id="__codelineno-10-11" name="__codelineno-10-11" href="#__codelineno-10-11"></a> <span class="n">best</span> <span class="o">=</span> <span class="nb">max</span><span class="p">(</span><span class="n">best</span><span class="p">,</span> <span class="n">right</span> <span class="o">-</span> <span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<a id="__codelineno-10-12" name="__codelineno-10-12" href="#__codelineno-10-12"></a>
<a id="__codelineno-10-13" name="__codelineno-10-13" href="#__codelineno-10-13"></a> <span class="k">return</span> <span class="n">best</span>
</code></pre></div>
<ul>
<li>
<p><strong>为什么需要 <code>char_index[char] &gt;= left</code></strong>：该字符可能来自当前窗口开始之前的映射。没有这个检查，你会错误地为当前窗口中实际不存在的字符收缩窗口。</p>
</li>
<li>
<p><strong>陷阱</strong>：使用集合并从左逐个删除字符是正确的但较慢。哈希表方法直接跳到正确的位置。</p>
</li>
</ul>
<h3 id="_16">困难：最小覆盖子串<a class="headerlink" href="#_16" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定字符串 <code>s</code> 和 <code>t</code>，在 <code>s</code> 中找到包含 <code>t</code> 中所有字符的最小窗口。</p>
</li>
<li>
<p><strong>模式</strong>：扩展窗口以包含所有必需的字符，然后从左侧收缩以找到最小有效窗口。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-11-1" name="__codelineno-11-1" href="#__codelineno-11-1"></a><span class="kn">from</span><span class="w"> </span><span class="nn">collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">Counter</span>
<a id="__codelineno-11-2" name="__codelineno-11-2" href="#__codelineno-11-2"></a>
<a id="__codelineno-11-3" name="__codelineno-11-3" href="#__codelineno-11-3"></a><span class="k">def</span><span class="w"> </span><span class="nf">min_window</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">t</span><span class="p">):</span>
<a id="__codelineno-11-4" name="__codelineno-11-4" href="#__codelineno-11-4"></a> <span class="k">if</span> <span class="ow">not</span> <span class="n">t</span> <span class="ow">or</span> <span class="ow">not</span> <span class="n">s</span><span class="p">:</span>
<a id="__codelineno-11-5" name="__codelineno-11-5" href="#__codelineno-11-5"></a> <span class="k">return</span> <span class="s2">&quot;&quot;</span>
<a id="__codelineno-11-6" name="__codelineno-11-6" href="#__codelineno-11-6"></a>
<a id="__codelineno-11-7" name="__codelineno-11-7" href="#__codelineno-11-7"></a> <span class="n">need</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">(</span><span class="n">t</span><span class="p">)</span> <span class="c1"># 我们需要的字符及其计数</span>
<a id="__codelineno-11-8" name="__codelineno-11-8" href="#__codelineno-11-8"></a> <span class="n">have</span> <span class="o">=</span> <span class="mi">0</span> <span class="c1"># 我们已经拥有足够数量的唯一字符数</span>
<a id="__codelineno-11-9" name="__codelineno-11-9" href="#__codelineno-11-9"></a> <span class="n">required</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">need</span><span class="p">)</span> <span class="c1"># 我们需要多少种唯一字符</span>
<a id="__codelineno-11-10" name="__codelineno-11-10" href="#__codelineno-11-10"></a>
<a id="__codelineno-11-11" name="__codelineno-11-11" href="#__codelineno-11-11"></a> <span class="n">left</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-11-12" name="__codelineno-11-12" href="#__codelineno-11-12"></a> <span class="n">best</span> <span class="o">=</span> <span class="p">(</span><span class="nb">float</span><span class="p">(</span><span class="s1">&#39;inf&#39;</span><span class="p">),</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="c1"># (长度, 左, 右)</span>
<a id="__codelineno-11-13" name="__codelineno-11-13" href="#__codelineno-11-13"></a>
<a id="__codelineno-11-14" name="__codelineno-11-14" href="#__codelineno-11-14"></a> <span class="n">window_counts</span> <span class="o">=</span> <span class="p">{}</span>
<a id="__codelineno-11-15" name="__codelineno-11-15" href="#__codelineno-11-15"></a>
<a id="__codelineno-11-16" name="__codelineno-11-16" href="#__codelineno-11-16"></a> <span class="k">for</span> <span class="n">right</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">s</span><span class="p">)):</span>
<a id="__codelineno-11-17" name="__codelineno-11-17" href="#__codelineno-11-17"></a> <span class="n">char</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">right</span><span class="p">]</span>
<a id="__codelineno-11-18" name="__codelineno-11-18" href="#__codelineno-11-18"></a> <span class="n">window_counts</span><span class="p">[</span><span class="n">char</span><span class="p">]</span> <span class="o">=</span> <span class="n">window_counts</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="n">char</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>
<a id="__codelineno-11-19" name="__codelineno-11-19" href="#__codelineno-11-19"></a>
<a id="__codelineno-11-20" name="__codelineno-11-20" href="#__codelineno-11-20"></a> <span class="c1"># 检查此字符的计数是否满足要求</span>
<a id="__codelineno-11-21" name="__codelineno-11-21" href="#__codelineno-11-21"></a> <span class="k">if</span> <span class="n">char</span> <span class="ow">in</span> <span class="n">need</span> <span class="ow">and</span> <span class="n">window_counts</span><span class="p">[</span><span class="n">char</span><span class="p">]</span> <span class="o">==</span> <span class="n">need</span><span class="p">[</span><span class="n">char</span><span class="p">]:</span>
<a id="__codelineno-11-22" name="__codelineno-11-22" href="#__codelineno-11-22"></a> <span class="n">have</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-11-23" name="__codelineno-11-23" href="#__codelineno-11-23"></a>
<a id="__codelineno-11-24" name="__codelineno-11-24" href="#__codelineno-11-24"></a> <span class="c1"># 当窗口有效时从左侧收缩</span>
<a id="__codelineno-11-25" name="__codelineno-11-25" href="#__codelineno-11-25"></a> <span class="k">while</span> <span class="n">have</span> <span class="o">==</span> <span class="n">required</span><span class="p">:</span>
<a id="__codelineno-11-26" name="__codelineno-11-26" href="#__codelineno-11-26"></a> <span class="c1"># 更新最佳值</span>
<a id="__codelineno-11-27" name="__codelineno-11-27" href="#__codelineno-11-27"></a> <span class="k">if</span> <span class="p">(</span><span class="n">right</span> <span class="o">-</span> <span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">best</span><span class="p">[</span><span class="mi">0</span><span class="p">]:</span>
<a id="__codelineno-11-28" name="__codelineno-11-28" href="#__codelineno-11-28"></a> <span class="n">best</span> <span class="o">=</span> <span class="p">(</span><span class="n">right</span> <span class="o">-</span> <span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">left</span><span class="p">,</span> <span class="n">right</span><span class="p">)</span>
<a id="__codelineno-11-29" name="__codelineno-11-29" href="#__codelineno-11-29"></a>
<a id="__codelineno-11-30" name="__codelineno-11-30" href="#__codelineno-11-30"></a> <span class="c1"># 移除最左边的字符</span>
<a id="__codelineno-11-31" name="__codelineno-11-31" href="#__codelineno-11-31"></a> <span class="n">left_char</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">left</span><span class="p">]</span>
<a id="__codelineno-11-32" name="__codelineno-11-32" href="#__codelineno-11-32"></a> <span class="n">window_counts</span><span class="p">[</span><span class="n">left_char</span><span class="p">]</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-11-33" name="__codelineno-11-33" href="#__codelineno-11-33"></a> <span class="k">if</span> <span class="n">left_char</span> <span class="ow">in</span> <span class="n">need</span> <span class="ow">and</span> <span class="n">window_counts</span><span class="p">[</span><span class="n">left_char</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">need</span><span class="p">[</span><span class="n">left_char</span><span class="p">]:</span>
<a id="__codelineno-11-34" name="__codelineno-11-34" href="#__codelineno-11-34"></a> <span class="n">have</span> <span class="o">-=</span> <span class="mi">1</span>
<a id="__codelineno-11-35" name="__codelineno-11-35" href="#__codelineno-11-35"></a> <span class="n">left</span> <span class="o">+=</span> <span class="mi">1</span>
<a id="__codelineno-11-36" name="__codelineno-11-36" href="#__codelineno-11-36"></a>
<a id="__codelineno-11-37" name="__codelineno-11-37" href="#__codelineno-11-37"></a> <span class="n">length</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span> <span class="o">=</span> <span class="n">best</span>
<a id="__codelineno-11-38" name="__codelineno-11-38" href="#__codelineno-11-38"></a> <span class="k">return</span> <span class="n">s</span><span class="p">[</span><span class="n">start</span><span class="p">:</span><span class="n">end</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="k">if</span> <span class="n">length</span> <span class="o">!=</span> <span class="nb">float</span><span class="p">(</span><span class="s1">&#39;inf&#39;</span><span class="p">)</span> <span class="k">else</span> <span class="s2">&quot;&quot;</span>
</code></pre></div>
<ul>
<li>
<p><strong>陷阱</strong>：<code>have</code> 计数器是关键优化。没有它，你需要在每一步比较整个 <code>window_counts</code> 字典与 <code>need</code>，每次比较是 <span class="arithmatex">\(O(|\text{unique chars}|)\)</span>。<code>have</code> 计数器使有效性检查变为 <span class="arithmatex">\(O(1)\)</span>。</p>
</li>
<li>
<p><strong>陷阱</strong>：检查 <code>window_counts[char] == need[char]</code>（而不是 <code>&gt;=</code>）确保我们每个字符只递增一次 <code>have</code>。如果使用 <code>&gt;=</code>，我们会多计数。</p>
</li>
</ul>
<hr />
<h2 id="_17">模式：前缀和<a class="headerlink" href="#_17" title="Permanent link">&para;</a></h2>
<ul>
<li><strong>前缀和</strong>数组存储累积和：<code>prefix[i] = sum(arr[0:i])</code>。一旦在 <span class="arithmatex">\(O(n)\)</span> 时间内构建完成，任何子数组和都可以在 <span class="arithmatex">\(O(1)\)</span> 时间内计算：<code>sum(arr[l:r]) = prefix[r] - prefix[l]</code>。</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-12-1" name="__codelineno-12-1" href="#__codelineno-12-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">build_prefix</span><span class="p">(</span><span class="n">arr</span><span class="p">):</span>
<a id="__codelineno-12-2" name="__codelineno-12-2" href="#__codelineno-12-2"></a> <span class="n">prefix</span> <span class="o">=</span> <span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">*</span> <span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">arr</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
<a id="__codelineno-12-3" name="__codelineno-12-3" href="#__codelineno-12-3"></a> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">arr</span><span class="p">)):</span>
<a id="__codelineno-12-4" name="__codelineno-12-4" href="#__codelineno-12-4"></a> <span class="n">prefix</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">prefix</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<a id="__codelineno-12-5" name="__codelineno-12-5" href="#__codelineno-12-5"></a> <span class="k">return</span> <span class="n">prefix</span>
<a id="__codelineno-12-6" name="__codelineno-12-6" href="#__codelineno-12-6"></a>
<a id="__codelineno-12-7" name="__codelineno-12-7" href="#__codelineno-12-7"></a><span class="c1"># arr[l:r] 的和（包含 l，不包含 r）</span>
<a id="__codelineno-12-8" name="__codelineno-12-8" href="#__codelineno-12-8"></a><span class="k">def</span><span class="w"> </span><span class="nf">range_sum</span><span class="p">(</span><span class="n">prefix</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">):</span>
<a id="__codelineno-12-9" name="__codelineno-12-9" href="#__codelineno-12-9"></a> <span class="k">return</span> <span class="n">prefix</span><span class="p">[</span><span class="n">r</span><span class="p">]</span> <span class="o">-</span> <span class="n">prefix</span><span class="p">[</span><span class="n">l</span><span class="p">]</span>
</code></pre></div>
<ul>
<li><strong>何时使用</strong>：问题涉及多个子数组和查询，或寻找具有特定和的子数组。</li>
</ul>
<h3 id="_18">简单：区间求和查询<a class="headerlink" href="#_18" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定一个数组，回答多个"从索引 <span class="arithmatex">\(l\)</span> 到 <span class="arithmatex">\(r\)</span> 的和是多少？"的查询。</p>
</li>
<li>
<p>没有前缀和：每个查询是 <span class="arithmatex">\(O(n)\)</span>。有前缀和：<span class="arithmatex">\(O(n)\)</span> 预计算，然后每个查询 <span class="arithmatex">\(O(1)\)</span>。</p>
</li>
</ul>
<h3 id="k">中等：和为 K 的子数组<a class="headerlink" href="#k" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：统计有多少个连续子数组的和等于 <span class="arithmatex">\(k\)</span>。</p>
</li>
<li>
<p><strong>模式洞察</strong>：从索引 <span class="arithmatex">\(l\)</span> 到 <span class="arithmatex">\(r\)</span> 的子数组和等于 <code>prefix[r+1] - prefix[l]</code>。我们希望这个值等于 <span class="arithmatex">\(k\)</span>，所以 <code>prefix[l] = prefix[r+1] - k</code>。对于每个位置，使用哈希表统计多少个更早的前缀和等于 <code>current_prefix - k</code>。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-13-1" name="__codelineno-13-1" href="#__codelineno-13-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">subarray_sum</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">k</span><span class="p">):</span>
<a id="__codelineno-13-2" name="__codelineno-13-2" href="#__codelineno-13-2"></a> <span class="n">count</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-13-3" name="__codelineno-13-3" href="#__codelineno-13-3"></a> <span class="n">prefix</span> <span class="o">=</span> <span class="mi">0</span>
<a id="__codelineno-13-4" name="__codelineno-13-4" href="#__codelineno-13-4"></a> <span class="n">prefix_counts</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">:</span> <span class="mi">1</span><span class="p">}</span> <span class="c1"># 空前缀和</span>
<a id="__codelineno-13-5" name="__codelineno-13-5" href="#__codelineno-13-5"></a>
<a id="__codelineno-13-6" name="__codelineno-13-6" href="#__codelineno-13-6"></a> <span class="k">for</span> <span class="n">num</span> <span class="ow">in</span> <span class="n">nums</span><span class="p">:</span>
<a id="__codelineno-13-7" name="__codelineno-13-7" href="#__codelineno-13-7"></a> <span class="n">prefix</span> <span class="o">+=</span> <span class="n">num</span>
<a id="__codelineno-13-8" name="__codelineno-13-8" href="#__codelineno-13-8"></a> <span class="c1"># 有多少更早的前缀和等于 prefix - k？</span>
<a id="__codelineno-13-9" name="__codelineno-13-9" href="#__codelineno-13-9"></a> <span class="n">count</span> <span class="o">+=</span> <span class="n">prefix_counts</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="n">prefix</span> <span class="o">-</span> <span class="n">k</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
<a id="__codelineno-13-10" name="__codelineno-13-10" href="#__codelineno-13-10"></a> <span class="n">prefix_counts</span><span class="p">[</span><span class="n">prefix</span><span class="p">]</span> <span class="o">=</span> <span class="n">prefix_counts</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="n">prefix</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>
<a id="__codelineno-13-11" name="__codelineno-13-11" href="#__codelineno-13-11"></a>
<a id="__codelineno-13-12" name="__codelineno-13-12" href="#__codelineno-13-12"></a> <span class="k">return</span> <span class="n">count</span>
</code></pre></div>
<ul>
<li>
<p>这结合了前缀和与哈希表查找：<span class="arithmatex">\(O(n)\)</span> 时间，<span class="arithmatex">\(O(n)\)</span> 空间。</p>
</li>
<li>
<p><strong>陷阱</strong>：忘记初始化 <code>prefix_counts = {0: 1}</code>。空前缀（在任何元素之前）的和为 0。没有它，你会漏掉从索引 0 开始的子数组。</p>
</li>
</ul>
<h3 id="_19">困难：除自身以外数组的乘积<a class="headerlink" href="#_19" title="Permanent link">&para;</a></h3>
<ul>
<li>
<p><strong>问题</strong>：给定一个数组，返回一个数组，其中每个元素是所有其他元素的乘积。你不能使用除法。</p>
</li>
<li>
<p><strong>模式</strong>：从左侧构建前缀乘积，从右侧构建后缀乘积。每个位置的答案是 <code>left_product * right_product</code>。</p>
</li>
</ul>
<div class="highlight"><pre><span></span><code><a id="__codelineno-14-1" name="__codelineno-14-1" href="#__codelineno-14-1"></a><span class="k">def</span><span class="w"> </span><span class="nf">product_except_self</span><span class="p">(</span><span class="n">nums</span><span class="p">):</span>
<a id="__codelineno-14-2" name="__codelineno-14-2" href="#__codelineno-14-2"></a> <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span>
<a id="__codelineno-14-3" name="__codelineno-14-3" href="#__codelineno-14-3"></a> <span class="n">result</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">n</span>
<a id="__codelineno-14-4" name="__codelineno-14-4" href="#__codelineno-14-4"></a>
<a id="__codelineno-14-5" name="__codelineno-14-5" href="#__codelineno-14-5"></a> <span class="c1"># 左向遍历：result[i] = nums[0..i-1] 的乘积</span>
<a id="__codelineno-14-6" name="__codelineno-14-6" href="#__codelineno-14-6"></a> <span class="n">prefix</span> <span class="o">=</span> <span class="mi">1</span>
<a id="__codelineno-14-7" name="__codelineno-14-7" href="#__codelineno-14-7"></a> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
<a id="__codelineno-14-8" name="__codelineno-14-8" href="#__codelineno-14-8"></a> <span class="n">result</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">prefix</span>
<a id="__codelineno-14-9" name="__codelineno-14-9" href="#__codelineno-14-9"></a> <span class="n">prefix</span> <span class="o">*=</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<a id="__codelineno-14-10" name="__codelineno-14-10" href="#__codelineno-14-10"></a>
<a id="__codelineno-14-11" name="__codelineno-14-11" href="#__codelineno-14-11"></a> <span class="c1"># 右向遍历：乘以 nums[i+1..n-1] 的乘积</span>
<a id="__codelineno-14-12" name="__codelineno-14-12" href="#__codelineno-14-12"></a> <span class="n">suffix</span> <span class="o">=</span> <span class="mi">1</span>
<a id="__codelineno-14-13" name="__codelineno-14-13" href="#__codelineno-14-13"></a> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">):</span>
<a id="__codelineno-14-14" name="__codelineno-14-14" href="#__codelineno-14-14"></a> <span class="n">result</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">*=</span> <span class="n">suffix</span>
<a id="__codelineno-14-15" name="__codelineno-14-15" href="#__codelineno-14-15"></a> <span class="n">suffix</span> <span class="o">*=</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
<a id="__codelineno-14-16" name="__codelineno-14-16" href="#__codelineno-14-16"></a>
<a id="__codelineno-14-17" name="__codelineno-14-17" href="#__codelineno-14-17"></a> <span class="k">return</span> <span class="n">result</span>
</code></pre></div>
<ul>
<li>
<p><span class="arithmatex">\(O(n)\)</span> 时间，<span class="arithmatex">\(O(1)\)</span> 额外空间（输出数组不计入）。它使用输出数组本身来存储中间前缀乘积，然后在第二遍遍历中乘入后缀乘积。</p>
</li>
<li>
<p><strong>陷阱</strong>：如果数组包含零，基于除法的方法会失败。这种前缀/后缀方法正确处理零，因为它从不做除法。</p>
</li>
</ul>
<hr />
<h2 id="_20">常见陷阱总结<a class="headerlink" href="#_20" title="Permanent link">&para;</a></h2>
<table>
<thead>
<tr>
<th>陷阱</th>
<th>示例</th>
<th>修复</th>
</tr>
</thead>
<tbody>
<tr>
<td>窗口大小的差一错误</td>
<td><code>right - left</code> vs <code>right - left + 1</code></td>
<td>画一个2元素示例</td>
</tr>
<tr>
<td>Python 中的可变默认值</td>
<td><code>def f(seen={})</code> 在调用间共享状态</td>
<td>使用 <code>def f(seen=None)</code></td>
</tr>
<tr>
<td>循环中的字符串拼接</td>
<td><code>s += c</code> 在 Python 中是 <span class="arithmatex">\(O(n^2)\)</span></td>
<td>使用 <code>list.append</code> + <code>"".join</code></td>
</tr>
<tr>
<td>前缀和中忘记 <code>{0: 1}</code></td>
<td>漏掉从索引 0 开始的子数组</td>
<td>始终用空前缀初始化</td>
</tr>
<tr>
<td>检查前添加哈希表</td>
<td>两数之和：在检查补数之前添加了 <code>num</code></td>
<td>先检查，后插入</td>
</tr>
<tr>
<td>未处理重复项</td>
<td>三数之和返回重复的三元组</td>
<td>跳过连续相等的值</td>
</tr>
<tr>
<td>整数溢出</td>
<td>C++/Java 中大数组求和</td>
<td>使用 <code>long</code> 或检查边界</td>
</tr>
</tbody>
</table>
<hr />
<h2 id="neetcode">课后练习题（NeetCode）<a class="headerlink" href="#neetcode" title="Permanent link">&para;</a></h2>
<p>按顺序练习。每道题强化本文件中的一个模式。</p>
<h3 id="_21">哈希表查找<a class="headerlink" href="#_21" title="Permanent link">&para;</a></h3>
<ul>
<li><a href="https://neetcode.io/problems/contains-duplicate">Contains Duplicate</a> — 热身：哈希集判断是否见过</li>
<li><a href="https://neetcode.io/problems/two-sum">Two Sum</a> — 补数查找</li>
<li><a href="https://neetcode.io/problems/anagram-groups">Group Anagrams</a> — 规范形式作为键</li>
<li><a href="https://neetcode.io/problems/top-k-elements-in-list">Top K Frequent Elements</a> — 哈希表 + 桶排序</li>
<li><a href="https://neetcode.io/problems/longest-consecutive-sequence">Longest Consecutive Sequence</a> — 哈希集配合序列起点技巧</li>
<li><a href="https://neetcode.io/problems/string-encode-and-decode">Encode and Decode Strings</a> — 设计序列化方案</li>
</ul>
<h3 id="_22">双指针<a class="headerlink" href="#_22" title="Permanent link">&para;</a></h3>
<ul>
<li><a href="https://neetcode.io/problems/is-palindrome">Valid Palindrome</a> — 向内指针</li>
<li><a href="https://neetcode.io/problems/two-integer-sum-ii">Two Sum II (sorted)</a> — 排序数组上的双指针</li>
<li><a href="https://neetcode.io/problems/three-integer-sum">Three Sum</a> — 固定 + 双指针 + 去重</li>
<li><a href="https://neetcode.io/problems/max-water-container">Container With Most Water</a> — 贪心双指针</li>
<li><a href="https://neetcode.io/problems/trapping-rain-water">Trapping Rain Water</a> — 带运行最大值的双指针</li>
</ul>
<h3 id="_23">滑动窗口<a class="headerlink" href="#_23" title="Permanent link">&para;</a></h3>
<ul>
<li><a href="https://neetcode.io/problems/buy-and-sell-crypto">Best Time to Buy and Sell Stock</a> — 退化窗口</li>
<li><a href="https://neetcode.io/problems/longest-substring-without-duplicates">Longest Substring Without Repeating Characters</a> — 扩展/收缩配合哈希表</li>
<li><a href="https://neetcode.io/problems/longest-repeating-substring-with-replacement">Longest Repeating Character Replacement</a> — 窗口 + 最大频率技巧</li>
<li><a href="https://neetcode.io/problems/minimum-window-with-characters">Minimum Window Substring</a> — 扩展到有效，收缩到最小</li>
</ul>
<h3 id="_24">前缀和<a class="headerlink" href="#_24" title="Permanent link">&para;</a></h3>
<ul>
<li><a href="https://neetcode.io/problems/products-of-array-discluding-self">Product of Array Except Self</a> — 前缀/后缀乘积</li>
</ul>
</article>
</div>
<script>var target=document.getElementById(location.hash.slice(1));target&&target.name&&(target.checked=target.name.startsWith("__tabbed_"))</script>
</div>
<button type="button" class="md-top md-icon" data-md-component="top" hidden>
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M13 20h-2V8l-5.5 5.5-1.42-1.42L12 4.16l7.92 7.92-1.42 1.42L13 8z"/></svg>
回到页面顶部
</button>
</main>
<footer class="md-footer">
<nav class="md-footer__inner md-grid" aria-label="页脚" >
<a href="../00.%20foundations/" class="md-footer__link md-footer__link--prev" aria-label="上一页: 基础">
<div class="md-footer__button md-icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11z"/></svg>
</div>
<div class="md-footer__title">
<span class="md-footer__direction">
上一页
</span>
<div class="md-ellipsis">
基础
</div>
</div>
</a>
<a href="../02.%20linked%20lists%2C%20stacks%2C%20and%20queues/" class="md-footer__link md-footer__link--next" aria-label="下一页: 链表、栈与队列">
<div class="md-footer__title">
<span class="md-footer__direction">
下一页
</span>
<div class="md-ellipsis">
链表、栈与队列
</div>
</div>
<div class="md-footer__button md-icon">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M4 11v2h12l-5.5 5.5 1.42 1.42L19.84 12l-7.92-7.92L10.5 5.5 16 11z"/></svg>
</div>
</a>
</nav>
<div class="md-footer-meta md-typeset">
<div class="md-footer-meta__inner md-grid">
<div class="md-copyright">
Made with
<a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
Material for MkDocs
</a>
</div>
<div class="md-social">
<a href="https://github.com/flykhan/maths-cs-ai-compendium-zh" target="_blank" rel="noopener" title="github.com" class="md-social__link">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><!--! Font Awesome Free 7.1.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2025 Fonticons, Inc.--><path d="M173.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6m-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3m44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9M252.8 8C114.1 8 8 113.3 8 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C436.2 457.8 504 362.9 504 252 504 113.3 391.5 8 252.8 8M105.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1m-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7m32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1m-11.4-14.7c-1.6 1-1.6 3.6 0 5.9s4.3 3.3 5.6 2.3c1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2"/></svg>
</a>
</div>
</div>
</div>
</footer>
</div>
<div class="md-dialog" data-md-component="dialog">
<div class="md-dialog__inner md-typeset"></div>
</div>
<script id="__config" type="application/json">{"annotate": null, "base": "../..", "features": ["navigation.tabs", "navigation.sections", "navigation.expand", "navigation.top", "navigation.footer", "search.suggest", "search.highlight", "content.code.copy", "toc.follow"], "search": "../../assets/javascripts/workers/search.2c215733.min.js", "tags": null, "translations": {"clipboard.copied": "\u5df2\u590d\u5236", "clipboard.copy": "\u590d\u5236", "search.result.more.one": "\u5728\u8be5\u9875\u4e0a\u8fd8\u6709 1 \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.more.other": "\u5728\u8be5\u9875\u4e0a\u8fd8\u6709 # \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.none": "\u6ca1\u6709\u627e\u5230\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.one": "\u627e\u5230 1 \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.other": "# \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.placeholder": "\u952e\u5165\u4ee5\u5f00\u59cb\u641c\u7d22", "search.result.term.missing": "\u7f3a\u5c11", "select.version": "\u9009\u62e9\u5f53\u524d\u7248\u672c"}, "version": null}</script>
<script src="../../assets/javascripts/bundle.79ae519e.min.js"></script>
<script src="../../javascripts/mathjax.js"></script>
<script src="https://unpkg.com/mathjax@3/es5/tex-mml-chtml.js"></script>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink