Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 18. 4Sum

---

參考資訊：
https://algo.monster/liteproblems/18

題目：


解答：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<vector<int>> ret;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < size - 3; ++i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) {
                continue;
            }

            for (int j = i + 1; j < size - 2; ++j) {
                if ((j > i + 1) && (nums[j] == nums[j - 1])) {
                    continue;
                }

                int l = j + 1;
                int r = size - 1;

                while (l < r) {
                    long long v = static_cast<long long>(nums[i]) + nums[j] + nums[l] + nums[r];

                    if (v == target) {
                        ret.push_back({ nums[i], nums[j], nums[l], nums[r] });

                        l += 1;
                        r -= 1;

                        while ((l < r) && (nums[l] == nums[l - 1])) {
                            l += 1;
                        }
                        while ((l < r) && (nums[r] == nums[r + 1])) {
                            r -= 1;
                        }
                    }
                    else if (v < target) {
                        l += 1;
                    }
                    else {
                        r -= 1;
                    }
                }
            }
        }

        return ret;
    }
};