【C++】競程筆記（雙指標）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
雙指標（Two-Pointer）
---
雙指標是一種常用於陣列或字串處理的技巧。
顧名思義，雙指標是指同時使用兩個指標（指向資料結構的索引）來遍歷或操作資料。
這種技巧可以減少時間複雜度，能避免掉多重迴圈，常被用在排序陣列或雙向搜尋的情況上。
常見的指標移動方式有：
* 一個從頭開始、另一個從尾開始（雙向靠攏）
* 一個快指標、另一個慢指標（追趕法）
* 同時向同一方向移動但控制條件不同
---
有一個更快理解什麼是雙指標的例子：
假設有個已經排序好的序列：`arr = [1, 3, 4, 5, 7, 10, 11]`。
我們希望能找出兩個數的和是 14。
則雙指標的初始狀態：`left → 1 3 4 5 7 10 11 ← right`
首先走第一遍初始狀態：`arr[left] + arr[right] = 12`，值太小，需要移動左邊的指標，叫他往右，讓值變大一點。
所以第二遍：`arr[left+1] + arr[right] = 14`，剛好就找到 14 了。
像這種就是 Two sum 問題。
### 例題 1
---
Leetcode 209. Minimum Size Subarray Sum：https://leetcode.com/problems/minimum-size-subarray-sum/description/
最開始會想到的一定都會是暴力解，如這題可用三重迴圈去解決，只是時間複雜度會變成 $O(N^3)$ 。具體解法：
1. 窮舉出所有 $(l, r)$
2. 求出所有 $num[l]$ 到 $num[r]$ 的數字總和
3. 看總和有沒有超過 $target$
雙指標做法：
1. 使用兩個指標：l 為左界，r 為右界，用來定義一個動態的區間 `[l, r]`。
2. r 從頭到尾遍歷陣列，每次將 `nums[r]` 加入目前的總和 sum。
3. 每當 `sum >= target` 時，表示目前這個區間 `[l, r]` 是一組解（其子陣列總和符合要求）。
4. 為了找到最短的子陣列和，就要把 l 往右推移，每推一次就更新當前最短長度，直到 `sum < target` 為止。
5. 重複步驟 2~4，直到整個陣列走完為止。
6. 若最後沒有找到任何子陣列和（即最短長度仍為初始最大值），則回傳 0。
範例程式碼：
```cpp=
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(); // 陣列長度
int l = 0, sum = 0;
int minLen = INT_MAX; // 最短的合法子陣列之長度
for (int r = 0; r < n; r ++){
sum += nums[r];
while (sum >= target){
// 為了找到最小子陣列和
// 所以把 l 右移
minLen = min(minLen, r - l + 1);
sum -= nums[l];
++l;
}
}
return (minLen == INT_MAX) ? 0 : minLen;
// minLen 從來沒變過，都還是 INT_MAX 的話，代表找不到子陣列和，回傳 0
}
```
時間複雜度： $O(n)$ 。
### 例題 2
---
Leetcode 167. Two Sum II - Input Array Is Sorted：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
解題思路：
1. 初始化兩個指標：`left = 0`、`right = numbers.size() - 1`。
2. 計算 `numbers[left] + numbers[right]`：
- 若和 `= target`：回傳 `left + 1` 和 `right + 1`（題目要求 1-indexed）。
- 若和 `< target`：表示數字太小，將 `left` 往右移動。
- 若和 `> target`：表示數字太大，將 `right` 往左移動。
3. 因為題目保證有唯一解，故不需考慮無解情況。
程式碼：
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0, r = numbers.size() - 1;
while (l < r){
int sum = numbers[l] + numbers[r];
if (sum == target){
return {l + 1, r + 1};
}
else if (sum < target){
l++;
}
else{
r--;
}
}
return {};
}
};
```
習題
---
1. Leetcode 3. Longest Substring Without Repeating Characters：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
解題思路：
1. 初始化雙指標 `l, r`。
2. 用 `unordered_set` 記錄目前的字元。
3. 當 `r` 指到重複的字元，就不斷地從 `l` 開始移除，直到移除掉所有重複的字元。
4. 每次更新最大長度。
```cpp=
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set <char> ch;
int l = 0, r = 0;
int maxLen = 0;
while (r < s.length()){
// find() 若找不到就指向 ch.end(), 代表這個字母沒出現過
if (ch.find(s[r]) == ch.end()){
ch.insert(s[r]);
maxLen = max(maxLen, r - l + 1);
r++;
}
else{
ch.erase(s[l]);
l++;
}
}
return maxLen;
}
};
```
2. Leetcode 977. Squares of a Sorted Array：https://leetcode.com/problems/squares-of-a-sorted-array/description/
解題思路：
原陣列 nums 為非遞減排序，負數平方後可能比正數平方大：
```
nums = [-4, -1, 0, 3, 10]
squares = [16, 1, 0, 9, 100]
```
若直接平方再排序的時間複雜度為 $O(nlogn)$ ，可用雙指標從兩端往中間夾，因為最大的平方數只可能出現在兩端。
1. 建立左右指標 `int l = 0, r = num.size() - 1;`。
2. 建立 result vector，從尾端填入最大的平方值（因為最大平方值在兩端）。
3. 每次比較 `abs(nums[left])` 和 `abs(nums[right])`，取較大者平方後放到 `result[i]`。
```cpp=
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size(); // 陣列長度
int l = 0, r = n - 1; // 左右指標
int index = n - 1; // 作為 result vector 的起始點, 也就是最右邊
// 另外要先塞最大的平方數, 再慢慢遞減下來 ( index-- )
vector<int> result(n);
while(l <= r){
if (abs(nums[l]) > abs(nums[r])){
result[index--] = nums[l] * nums[l];
l ++;
}
else{
result[index--] = nums[r] * nums[r];
r --;
}
}
return result;
}
};
```
Sign in with Wallet
Connect another wallet