題目: LeetCode - 18. 4Sum
解題思路
基本上和 LeetCode - 15 解題紀錄 的想法相同,只是要固定的點從一個變兩個,11 行和 12 行的兩個判斷是為了使執行速度更快,由於陣列是排序過的,所以 11 行的條件成立表後面的 nums[i]
都不可能符合條件,若 12 行的條件成立表 nums[i]
太小,直接往後做即可。
參考解法
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
| class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n = nums.size(); vector<vector<int>> v; sort(nums.begin(), nums.end()); for (int i = 0; i < n - 3; ++i) { if (i && nums[i] == nums[i - 1]) continue; if (0L + nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; if (0L + nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; for (int j = n - 1; j > i + 2; --j) { if (j != n - 1 && nums[j] == nums[j + 1]) continue; int targetVal = target - (nums[i] + nums[j]); int l = i + 1, r = j - 1; while (l < r) { if (nums[l] + nums[r] == targetVal) { v.push_back({ nums[i], nums[l], nums[r], nums[j] }); 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] < targetVal) ++l; else --r; } } } return v; } };
|