[LeetCode] 為何不用 Two Pointers 來寫第一題? #1 Two Sum
LeetCode 有一堆題目都很愛用 two pointers，為何第一題不用一下呢?
用 Two Pointers 會遇到什麼問題
用 two pointers 前通常要確保 arrays 是排序好的，這一題的 input 並沒有排序好。(two pointers 的原理可以看 #16 前面有做過解釋)
就算我們先排序好了，會發生什麼事? 像底下這樣:
因為題目要輸出兩個數的 indexes，看起來好像很 OK 但是馬上就會得到 wrong answer:
喔不! vector 被排序後的 indexes 和原來的不一樣了，正確答案應該是第 0 和第 2 個位置才對。
解決方法
怎麼辦? 這其實可以用一個還滿常用到的技巧，就是把 (number, index) 一起下去做 sorting:
我們把 number 和 index 綁在一起，任何人都不能拆散他們。做排序的時候就按照 number 來排序，這樣他們不管被怎麼排我們都還能知道原來的 index 是多少。
解法1: 用客製化的資料結構把他們綁在一起
這對我來說是最乾淨、不會出錯的方式，我們先定義一個 struct 叫做 Item:
struct Item {
int num = 0;
int index = 0;
};
當我們在做 sorting 的時候就依照 num 來比較:
std::sort(items.begin(), items.end(),
[](const Item &item1, const Item &item2) {
return item1.num < item2.num;
});
最後再用 two pointers，所以完整的 C++ 程式碼就會是這樣:
struct Item {
int num = 0;
int index = 0;
};
class Solution {
public:
std::vector<int> twoSum(std::vector<int> &nums, int target) {
const int sz = (int)nums.size();
std::vector<Item> items(sz);
for (int i = 0; i < sz; i++) {
items[i].num = nums[i];
items[i].index = i;
}
// Sort the items by numbers
std::sort(items.begin(), items.end(),
[](const Item &item1, const Item &item2) {
return item1.num < item2.num;
});
int left = 0, right = sz - 1;
while (left < right) {
const int sum = items[left].num + items[right].num;
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return {items[left].index, items[right].index};
}
}
return {}; // Should not happen
}
};
其他程式語言都可以用類似的方式達成，是不是很清爽的解答呢?
Submit 完就得到還可以的 runtime:
解法2: 只 Sort Indexes
另外一種方法是我們把用什麼來排序 (數字) 和排序的對象 (index) 分開來，不要綁在一起。
好處就是我們可以讓原來的 nums 維持原樣。如果原來要做 sorting 現在不是數字，可能是一個 object 要搬來搬去可能就會比較慢，但我們這樣做只會讓一個小小的 index 搬來搬去，就可能會比較快。
但要怎麼做? 我每次也忘記，所以我們先去 Google "C++ sort vector with indexes"，就會找到一個 StackOverflow 的解答，然後我們就套用到我們的程式裡:
class Solution {
public:
std::vector<int> twoSum(std::vector<int> &nums, int target) {
const int sz = (int)nums.size();
std::vector<int> indexes(sz);
// Fill indexes with 0, 1, 2, ...
std::iota(indexes.begin(), indexes.end(), 0);
// Sort the indexes by numbers
std::stable_sort(indexes.begin(), indexes.end(),
[&nums](const int i1, const int i2) {
return nums[i1] < nums[i2];
});
int left = 0, right = sz - 1;
while (left < right) {
const int sum = nums[indexes[left]] + nums[indexes[right]];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return {indexes[left], indexes[right]};
}
}
return {}; // Should not happen
}
};
優點:
- 速度會比較快，因為要排序的東西變少了
- 程式碼比較短
- 不用創特殊的資料結構來裝東西
缺點當然也很明顯:
- 程式碼不好讀，比較不好維護
- Debug 會比較困難，因為 debug 途中你還要用 index 回去找原本的東西
這邊要用 std::sort 或 std::stable_sort 其實都可以，因為 LeetCode 說解答只有一個，所以我們不用費心去管兩個數字相同但 index 卻不一樣的狀況。
Submit 完速度差不多，因為這題的資料並不複雜:
結語
這題我總共寫了 6 種寫法，雖然方式完全不同，速度卻大同小異。
在先前的文章中我還自己寫了一個簡單的 hashmap 來做這一題，再用 Callgrind 來加速。
比 LeetCode 解答好的地方就在於這個解答沒有用到複雜的 map/unordered_map，我們只用了 vector + sort 就做完了。
留言
發佈留言