APCSer
    • Create new note
    • Create a note from template
      • Sharing URL Link copied
      • /edit
      • View mode
        • Edit mode
        • View mode
        • Book mode
        • Slide mode
        Edit mode View mode Book mode Slide mode
      • Customize slides
      • Note Permission
      • Read
        • Only me
        • Signed-in users
        • Everyone
        Only me Signed-in users Everyone
      • Write
        • Only me
        • Signed-in users
        • Everyone
        Only me Signed-in users Everyone
      • Engagement control Commenting, Suggest edit, Emoji Reply
      • Invitee
    • Publish Note

      Share your work with the world Congratulations! 🎉 Your note is out in the world Publish Note

      Your note will be visible on your profile and discoverable by anyone.
      Your note is now live.
      This note is visible on your profile and discoverable online.
      Everyone on the web can find and read all notes of this public team.
      See published notes
      Unpublish note
      Please check the box to agree to the Community Guidelines.
      View profile
    • Commenting
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
      • Everyone
    • Suggest edit
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
    • Emoji Reply
    • Enable
    • Versions and GitHub Sync
    • Note settings
    • Engagement control
    • Transfer ownership
    • Delete this note
    • Save as template
    • Insert from template
    • Import from
      • Dropbox
      • Google Drive
      • Gist
      • Clipboard
    • Export to
      • Dropbox
      • Google Drive
      • Gist
    • Download
      • Markdown
      • HTML
      • Raw HTML
Menu Note settings Sharing URL Create Help
Create Create new note Create a note from template
Menu
Options
Versions and GitHub Sync Engagement control Transfer ownership Delete this note
Import from
Dropbox Google Drive Gist Clipboard
Export to
Dropbox Google Drive Gist
Download
Markdown HTML Raw HTML
Back
Sharing URL Link copied
/edit
View mode
  • Edit mode
  • View mode
  • Book mode
  • Slide mode
Edit mode View mode Book mode Slide mode
Customize slides
Note Permission
Read
Only me
  • Only me
  • Signed-in users
  • Everyone
Only me Signed-in users Everyone
Write
Only me
  • Only me
  • Signed-in users
  • Everyone
Only me Signed-in users Everyone
Engagement control Commenting, Suggest edit, Emoji Reply
Invitee
Publish Note

Share your work with the world Congratulations! 🎉 Your note is out in the world Publish Note

Your note will be visible on your profile and discoverable by anyone.
Your note is now live.
This note is visible on your profile and discoverable online.
Everyone on the web can find and read all notes of this public team.
See published notes
Unpublish note
Please check the box to agree to the Community Guidelines.
View profile
Engagement control
Commenting
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
  • Everyone
Suggest edit
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
Emoji Reply
Enable
Import from Dropbox Google Drive Gist Clipboard
   owned this note    owned this note      
Published Linked with GitHub
Subscribed
  • Any changes
    Be notified of any changes
  • Mention me
    Be notified of mention me
  • Unsubscribe
Subscribe
## 概念 在[基礎概念](/HJTzt0Zdll)已經講過雙指針的概念與應用類型,以下就是拿常見的類型去解說 ## Sliding window 用兩個指標去維護一個區間,然後讓這個區間往左右移動,或是讓區間的大小變動 若是區間左右移動,代表兩個指標的相對移動是 $0$,代表都往左移(或都往右移) $i$ 格 若是區間大小變動,那代表兩個指標更靠近或更遠了 ### 與題目對應概念 由於 Sliding window 的概念是用兩個指標(指針)維護一個區間,區間換句話說也可以是 1. (連續 continue) 子陣列(subarray) 2. (連續 continue) 區段(section) 3. (連續 continue) 子字串(substring) 所以在這些用詞出現的時候,就可以考慮一下是否是 Sliding window 的問題 而當題目還多出現以下概念的時候,基本就可以確定是 Sliding window 了 1. 固定長度 $\rightarrow$ 快速更新區間值 2. 可變長度 $\rightarrow$ 動態收縮、擴大區間 3. 區間內特定值出現頻率統計 $\rightarrow$ 與 map 輔助使用 4. 環形處理 $\rightarrow$ 複製陣列 5. 極值維護 $\rightarrow$ 具單調性的資料結構 ### 例題-Leetcode 643. Maximum Average Subarray I 給定一個由 $n$ 個整數組成的陣列`nums`和一個整數 $k$,找出所有長度為 $k$ 的連續子陣列 其中的子陣列值平均稱為 $X_i$,求最大的 $X_i$,誤差小於 $10^{-5}$ 的答案都可以 這題就是固定長度區間例題,整個區間往右移動就可以計算出所有答案,舉個例子 假設原本是區間`nums[0 ~ k-1]`,下一個區間應該是`nums[1 ~ k]`,如果重新計算 那每次都需要找 $k$ 個位置,但如果用上一個區間把`nums[0]`減去,再加上`nums[k]` 這樣相當於就是區間`nums[1 ~ k]`,其他區間也可以用同一個辦法推出來 ```cpp= class Solution { public: double findMaxAverage(vector<int>& nums, int k) { double max_n = -100000 ; // 當前最大平均 int p1 = 0, p2 = k-1, sum = 0, len = nums.size() ; for (int i=p1;i<=p2;i++) // 計算第一個區間 sum += nums[i] ; max_n = (double)sum/k ; while (p2<len-1) { // 計算出所有區間 sum = sum - nums[p1++] + nums[++p2] ; double tmp = (double)sum/k ; max_n = (max_n > tmp) ? max_n : tmp ; // 更新最大平均 } return max_n ; } }; ``` ### 例題-Leetcode 209. Minimum Size Subarray Sum 給定一個正整數陣列`nums`和一個正整數`target` 找出一個最短的連續子陣列,使該子陣列的值總和大於等於`target`,如果不存在答案就回傳 $0$ 這題是用可變長度的 Sliding window,整個策略會像是下面敘述的 1. 從最開頭開始長度 $1$ 的區間 2. 如果目前總和小於 $k$,就擴充區間,所以右方的指標往右 3. 如果目前總和大於等於 $k$,就縮減區間(左指標右移),如果區間已經是 $1$ 了就直接回傳 ```cpp= class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int len = nums.size(), min_len, sum, p1 = 0, p2 = 0 ; min_len = len + 1 ; sum = nums[0] ; while (p2 < len) { if (sum >= target) { // 區間和滿足條件 min_len = min(min_len, p2-p1+1) ; if (p1 < p2) { // 縮減範圍 sum -= nums[p1] ; p1++ ; } else return 1 ; // 最小範圍是 1 } else { if (p2 < len-1) // 擴大範圍 sum += nums[++p2] ; else p2++ ; } } if (min_len == len+1) return 0 ; // 無答案 return min_len ; } }; ``` 這個演算法能成功找出答案的原因是它把右指標當成一種固定終點了 導致每次右指標變動的時候,我們都是在求"以右指標作為終點,找出符合條件的連續子陣列" 而右指標一定會走過每個位置 $\rightarrow$ 每個位置作為終點的答案都找出來了 最後只要加上簡單的比較就可以知道整個陣列的答案 ### 例題-Leetcode 3. Longest Substring Without Repeating Characters 給定一個字串`S`,找出不含重複字元的最長子字串 這題要找不含重複字元的最長子字串,所以區間長度是會變動的 因為有"不含重複字元"的條件,所以我們需要紀錄當前區間的每個字母的數量 可以用 map(哈希表) 來實作,如果字串中元素只有大小寫字母的話 也可以用 `小寫字母-'a'` 作為 index 的方式用 array 紀錄 (其實這題可以用 $256$ 格的 array 處理,但用 map 比較適合學習) 但是這題還有數字、空格等其他元素所以採用哈希表的方式 實際的策略其實就兩個 : 1. 如果當前區間會造成重複字元,那就將範圍縮減,左指標右移動直到不含重複字元 2. 前一個步驟做完後當前區間不含重複字元,試圖擴張區間,右指標右移 ```cpp= class Solution { public: int lengthOfLongestSubstring(string s) { vector<int> cnt(26, 0) ; // p1, p2 左右指標、slen 當前子字串長度、max_len 當前答案 int p1 = 0, p2 = 0, len = s.size(), slen = 0, max_len = 1 ; if (len == 0) return 0 ; // 注意空字串的特例 unordered_map<char, int> mp ; mp[s[0]] = 1 ; p2++, slen++ ; while (p2 < len) { // 如果當前區間會造成重複字元 if (mp.find(s[p2]) != mp.end() && mp[s[p2]] == 1) while (mp[s[p2]] == 1) // 縮減區間直到不含重複字元 mp[s[p1++]]--, slen-- ; mp[s[p2]] = 1 ; slen++, p2++ ; // 擴張區間 max_len = max(max_len, slen) ; } return max_len ; } }; ``` 其實透過這兩題變動區間,我想傳達的概念是變動區間有點像是把右指標當成固定終點來看 比如這題就是假設以第 $i$ 個字元作為子字串的結尾,找出最長符合條件的子字串 因為右指標一定會走過每個字元,那答案就會在某個字元時出現,換句話說 最終答案對應的子字串結尾,一定是題目給定的字串終某個字元 而 Sliding window 可以找出每個字元做結尾時的答案 加上簡單的比較就一定可以找出答案 ### 例題-Leetcode 560. Subarray Sum Equals K 給定一個整數陣列`nums`和一個整數`k`,回傳子陣列總和等於 $k$ 的個數 這題雖然看起來跟之前的題目沒什麼兩樣,但其實這裡有兩個要注意的地方 1. 含負數,代表左指標盲目地左移可能是錯誤的 2. 要回傳的不是子陣列的長度,而是總和為 $k$ 的子陣列數量 所以我們不能在用之前那種方式去解,這時候我們可以轉換一下思路 計算區間和的方法除了一個個慢慢計算之外還有前綴和,前綴和可以透過兩點差值來計算兩點區間和 當然這裡有指定區間和要是 $K$,所以我們可以得出下列公式 `prefix[j+1]-prefix[i] = k -> prefix[j+1]-k = prefix[i]` 從這個公式就可以知道,對於某點 $j+1$,我們要找出它之前的所有滿足公式的 $i$ 找的方式也很簡單,一樣用哈希表去記錄哪些前綴和(特定數字)出現過幾次 ```cpp= class Solution { public: int subarraySum(vector<int>& nums, int k) { int len = nums.size() ; vector<int> prefix(len+1, 0) ; // 計算前綴和 for (int i=0;i<len;i++) prefix[i+1] = prefix[i] + nums[i] ; int p1 = 0, p2 = 1, ans = 0 ; unordered_map<int, int> mp ; mp[0] = 1 ; // 注意前綴和的第一個元素是 0 while (p2 <= len) { int tmp = prefix[p2] - k ; // 區間和為 k 的對應前綴和 if (mp.find(tmp) != mp.end()) // 找到了 ans += mp[tmp] ; if (mp.find(prefix[p2]) == mp.end()) // 將前綴和放入 map mp[prefix[p2]] = 0 ; mp[prefix[p2]]++, p2++ ; // 擴充區間 } return ans ; } }; ``` 這題的概念是 Sliding window 在前綴和當中的應用,不過你仔細看就會發現 我定義的 $p1$ 完全沒有變動,因為這裡在前墜和的概念是右指標只能在區間`[p1, p2]`找想要的值 但實際區間和對應的區間應該是`[x, p2]`,這裡的 $x$ 會限定在區間`[p1, p2]` 內 而實際的 $x$ 值我們也不知道,我們只能透過公式+哈希表找到有多少 $x$ 符合條件 ### 例題-Leetcode 239. Sliding Window Maximum 給定一個整數陣列`nums`,有一個大小為 $k$ 的 Sliding window 從陣列的最左邊移到最右邊 你只能看到 $k$ 個數字,每次移動 Sliding window 都會向右一個位置 把每個 Sliding window 中的最大值存到一個 vector 中回傳 這算是比較困難的問題了,如果不同 Sliding window 就重新計算的話,複雜度會是 $O(nk)$ 其實這個問題會涉及到另外一個概念-單調 deque,因為我們不斷往右,且需要最大值 我們可以先簡化一下問題,求出一個陣列中某元素 $X$ 左方第一個大於 $X$ 的值對應的位置 說的有點複雜,簡單來說假設陣列為`{6,5,4,3}`,那 $3$ 左方第一個大於 $3$ 的數字就是 $4$ 找的方式也很簡單,從左往右找大於 $3$ 的值最後出現在哪裡就好,但是當這個問題拓展了 不只要求某一個元素,而是要求多個元素,這個方法就會變得特別沒效率,所以我們轉換一下思路 左方大於 $X$ 的第一個值,那我們其實在不確定 $X$ 的情況下,先把所有值都存進去 deque 但是很明顯,假設陣列為`{3,4,x}`,那 $3$ 根本就不需要放進去,可以證明一下 * 假設 $x \ge 4$,那不管是 $4$ 還是"比 $4$ 還小的" $3$ 都沒用 * 假設 $x < 4$,那一樣會先找到 $4$ 由此可知,維護這個簡化後問題的單調 deque 就需要保證幾點 1. 如果當前數字大於等於之前 deque 存的值,把那些值都丟掉(因為用不到),然後放入當前數字 2. 如果當前數字小於之前 deque 存的值,由於不確定 $x$ 的大小,所以當前數字直接存入 deque 回到原本的題目,由於我們多了一個 Sliding window,所以這個還需要確保數字在範圍內 所以每次移動都要判斷 deque 最左方(相對最早進入)的值是否已經在範圍外了 基於這個原因,我們應該儲存 index,因為 index 可以判斷是否在範圍外,也可以找出值 ```cpp= class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq ; vector<int> result ; int len = nums.size() ; for (int i=0;i<len;i++) { // 確保數字還在 Sliding window 範圍內 if (!dq.empty() && dq.front() == i-k) dq.pop_front() ; // 去除比當前數字還小的值 while(!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back() ; // 儲存當前數的 index dq.push_back(i) ; if (i >= k-1) // 將當前最大值放入答案 result.push_back(nums[dq.front()]) ; } return result ; } }; ``` ## 相向指針 相向指針就是互相靠近的雙指針,基本上會有三個使用前提 1. 資料是可排序/已排序的 2. 可以透過"縮小範圍"來找出最終的答案 3. 單調性條件成立 其實第一個跟第三個可以當作是一樣的 而單調性也是大部分題目可以用相向指針解題的關鍵 ### 與題目對應概念 * 與 $K$ 值相同的兩/三數和 * 最小差值、與 $K$ 值相近... * 長短不一找最大面積長方形 * 區間合併 * 字串操作 基本上前四個有的就可以考慮看看是否可以用相向指針去解 最後一個字串操作可能是迴文、反轉之類的,相對比較直觀 ### Leetcode 167. Two Sum II – Input Array Is Sorted {%hackmd Hyxk8LAT0 %} ### Leetcode 15. 3Sum {%hackmd Bk05L_Njlx %} ### Leetcode 16. 3Sum Closest {%hackmd S1aY0ANjxe %}

Import from clipboard

Paste your markdown or webpage here...

Advanced permission required

Your current role can only read. Ask the system administrator to acquire write and comment permission.

This team is disabled

Sorry, this team is disabled. You can't edit this note.

This note is locked

Sorry, only owner can edit this note.

Reach the limit

Sorry, you've reached the max length this note can be.
Please reduce the content or divide it to more notes, thank you!

Import from Gist

Import from Snippet

or

Export to Snippet

Are you sure?

Do you really want to delete this note?
All users will lose their connection.

Create a note from template

Create a note from template

Oops...
This template has been removed or transferred.
Upgrade
All
  • All
  • Team
No template.

Create a template

Upgrade

Delete template

Do you really want to delete this template?
Turn this template into a regular note and keep its content, versions, and comments.

This page need refresh

You have an incompatible client version.
Refresh to update.
New version available!
See releases notes here
Refresh to enjoy new features.
Your user state has changed.
Refresh to load new user state.

Sign in

Forgot password

or

By clicking below, you agree to our terms of service.

Sign in via Facebook Sign in via Twitter Sign in via GitHub Sign in via Dropbox Sign in with Wallet
Wallet ( )
Connect another wallet

New to HackMD? Sign up

Help

  • English
  • 中文
  • Français
  • Deutsch
  • 日本語
  • Español
  • Català
  • Ελληνικά
  • Português
  • italiano
  • Türkçe
  • Русский
  • Nederlands
  • hrvatski jezik
  • język polski
  • Українська
  • हिन्दी
  • svenska
  • Esperanto
  • dansk

Documents

Help & Tutorial

How to use Book mode

Slide Example

API Docs

Edit in VSCode

Install browser extension

Contacts

Feedback

Discord

Send us email

Resources

Releases

Pricing

Blog

Policy

Terms

Privacy

Cheatsheet

Syntax Example Reference
# Header Header 基本排版
- Unordered List
  • Unordered List
1. Ordered List
  1. Ordered List
- [ ] Todo List
  • Todo List
> Blockquote
Blockquote
**Bold font** Bold font
*Italics font* Italics font
~~Strikethrough~~ Strikethrough
19^th^ 19th
H~2~O H2O
++Inserted text++ Inserted text
==Marked text== Marked text
[link text](https:// "title") Link
![image alt](https:// "title") Image
`Code` Code 在筆記中貼入程式碼
```javascript
var i = 0;
```
var i = 0;
:smile: :smile: Emoji list
{%youtube youtube_id %} Externals
$L^aT_eX$ LaTeX
:::info
This is a alert area.
:::

This is a alert area.

Versions and GitHub Sync
Get Full History Access

  • Edit version name
  • Delete

revision author avatar     named on  

More Less

Note content is identical to the latest version.
Compare
    Choose a version
    No search result
    Version not found
Sign in to link this note to GitHub
Learn more
This note is not linked with GitHub
 

Feedback

Submission failed, please try again

Thanks for your support.

On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

Please give us some advice and help us improve HackMD.

 

Thanks for your feedback

Remove version name

Do you want to remove this version name and description?

Transfer ownership

Transfer to
    Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

      Link with GitHub

      Please authorize HackMD on GitHub
      • Please sign in to GitHub and install the HackMD app on your GitHub repo.
      • HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.
      Learn more  Sign in to GitHub

      Push the note to GitHub Push to GitHub Pull a file from GitHub

        Authorize again
       

      Choose which file to push to

      Select repo
      Refresh Authorize more repos
      Select branch
      Select file
      Select branch
      Choose version(s) to push
      • Save a new version and push
      • Choose from existing versions
      Include title and tags
      Available push count

      Pull from GitHub

       
      File from GitHub
      File from HackMD

      GitHub Link Settings

      File linked

      Linked by
      File path
      Last synced branch
      Available push count

      Danger Zone

      Unlink
      You will no longer receive notification when GitHub file changes after unlink.

      Syncing

      Push failed

      Push successfully