[LeetCode] 讓 Two Pointers 解法更快的技巧 #16 3Sum Closest
上一篇我們用數學分析讓 3Sum 快 2 倍，這題也有辦法用數學加快嗎? 當然可以。
為什麼 Two Pointers 可以這樣用?
在數學分析前我們還是要來先了解一下為什麼 two pointers 會有用，如果只知道用卻不知道為什麼可以這樣用，面試時簡單問一句就會被考倒。
答案很簡單，如果我們要找比較小的數字，移動錯指標的話完全沒有幫助:
同理如果我們要找更大的數字，移動指到比較大的數字的指標也沒有幫助:
這其實和 LeetCode #11 的移動原理非常像。
什麼時候根本不用跑 Two Pointers?
如果第一個數字 A 固定的話，A+B+C 最小和最大的數值會是一開始跑和準備結束的時候:
如果我們想要找 A+B+C ≈ 300，中間的結果一定介於 [60, 180] 之間，我們幹嘛去跑 two pointers?
我們其實只要算一下最小和最大的可能性就可以決定要不要用 two pointers。
如果之後 A 固定住，我們要找 B+C ≈ 200，同理我們也可以先算最小和最大值來決定要不要跳過:
像這個例子 LeetCode 第二個解答就用 binary search，那我們知道範圍的話連跑都不用跑。
最後一個要提的陷阱就是我們可能會以為 wow 這樣做是不是 O(N) 因為我們可以直接找到 A 在哪裡，然後就去找 B+C 也是 O(N)。
但其實不是，因為我們可能會發現要找的目標可能會在很多範圍內:
而且我們也沒辦法事前知道我們要跑多少個 range，有可能完全沒有，也有可能全部都要跑。所以這解法只是優化過後的 O(N^2) 演算法。
優化: 暴力解
用 3 個 for loop 傻傻地去試所有組合的話結果就會很慢 (C++ code on GitHub):
但如果我們套用上面的優化之後結果就會快 2 倍 (C++ code on GitHub):
優化: Two Pointers 解
優化 two pointers 和沒有優化的版本其實只差了 8 行而已，優化的版本會長這樣子:
class Solution {
public:
int threeSumClosest(std::vector<int> &nums, int target) {
std::sort(nums.begin(), nums.end());
const int sz = (int)nums.size();
for (int i = 0; i < sz - 2; i++) {
const int lowestSum = nums[i] + nums[i + 1] + nums[i + 2];
const int highestSum = nums[i] + nums[sz - 2] + nums[sz - 1];
if (lowestSum <= target && target <= highestSum) {
twoSumClosest(nums, target, i + 1);
} else {
checkCloser(nums, target, lowestSum);
checkCloser(nums, target, highestSum);
}
}
return m_closestSum;
}
void twoSumClosest(std::vector<int> &nums, const int target, int left) {
const int num1 = nums[left - 1];
int right = (int)nums.size() - 1;
while (left < right) {
const int sum = num1 + nums[left] + nums[right];
checkCloser(nums, target, sum);
if (sum < target) {
left++;
} else {
right--;
}
}
}
void checkCloser(const std::vector<int> &nums, const int target,
const int sum) {
const int diff = std::abs(sum - target);
if (diff < m_minDiff) {
m_closestSum = sum;
m_minDiff = diff;
}
}
int m_closestSum = 0;
int m_minDiff = 99999;
};
優化的部分只有 8-15 行，其他都是原本 two pointers 的作法。
作法也很簡單，我們先算算看兩邊的端點，目標有在範圍裡面就去跑 two pointers 吧，沒有在範圍裡面我們就看看兩邊的端點是不是比較靠近目標。
有快很多?
沒優化的版本花了 12ms:
優化過後的版本花了 8ms:
那些寫到 0ms 的人就會覺得嗤之以鼻，什麼嘛也才快 4ms 有什麼好說的。但是這題目的 constraints 實在太小，所以看不出差異，如果我們把資料量 scale up 會發生什麼事呢?
真的快很多
於是我就寫了一個 benchmark 的程式碼，把題目敘述的 constraints 慢慢 scale up 2 倍、4 倍、8 倍... 比較看看兩個版本的速度。
結果資料量越大的話差異果然就很明顯:
當然這速度會根據資料的狀況有所差異，運氣好甚至 scale=16 的時候優化的版本竟然只花了 13ms，沒優化的慢了 67 倍 (數據資料)！有多誇張。
所以說這個優化可能在現實 project 上會比較有幫助。
進階優化
看了 code 你可能會發現雖然我們上面那樣講，但是其實還有兩個優化我們卻沒有做:
- 找 A+B+C 的 range 其實可以用 binary search 找到第一個符合資格的 range 和最後一個，因為他們就像 Google Maps 的 schedule explorer 功能一樣
- 我們 code 沒有做 B+C 先檢查 endpoints
結語
其實在寫 3Sum 題目之前我還真的從來沒碰過 two pointers，所以上一篇 3Sum 我就有點排斥用 two pointers 來寫，不過反而找到更快的解法。
仔細看了一下才發現原來 LeetCode #11 我早就破解過 two pointers 了。
這次數學又得了一分，寫程式要不要學數學? 我想是肯定的，畢竟數學可以幫助你設計更好更快的演算法。
留言
發佈留言