題目: LeetCode - 15. 3Sum
題目說明
給一個陣列,求此陣列中所有三個元素值相加為 0 的組合。
解題思路
為了增加效率,先對陣列進行排序,接著遍歷陣列,先選定一個最左邊的數字,接著往右找是否存在相加為此數的相反數的組合,若存在代表找到一組,接著檢查 l
的右邊及 r
的左邊的數是否相同,避免找到重複的組合。同時再過程中若是 nums[i] > 0
就可以不用再找了,因為我們是選定最左邊的數,且我們的陣列是排序過的,所以右邊不可能會有相加為此數的相反數的組合,同時要避免重複運算,所以若 nums[i] == nums[i - 1]
則直接 continue
。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| static auto __ = []() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }();
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n = nums.size(); vector<vector<int>> v; sort(nums.begin(), nums.end()); for (int i = 0; i < n - 2; ++i) { if (nums[i] > 0) break; if (i && nums[i] == nums[i - 1]) continue; int target = -nums[i], l = i + 1, r = n - 1; while (l < r) { if (nums[l] + nums[r] == target) { v.push_back({ nums[i], nums[l], nums[r] }); while(l < r && nums[l] == nums[l + 1]) ++l; while(l < r && nums[r] == nums[r - 1]) --r; ++l, --r; } else if (nums[l] + nums[r] < target) ++l; else --r; } } return v; } };
|