[LeetCode] 15. 3sum [C/C++] Two Pointer

https://leetcode.com/problems/3sum/submissions/

3Sum - LeetCode

코드 1

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> s;
        int cnt = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            int l = i + 1; int r = nums.size() - 1;
            while (l < r) {
                if (nums[l] + nums[r] == -nums[i]) {
                    s.insert({nums[i], nums[l], nums[r]});
                    if (nums[l] == nums[r]) break;
                    l++;
                }
                else if (nums[l] + nums[r] < -nums[i]) l++;
                else r--;
            }
        }
        vector<vector<int>> res;
        for (auto iter = s.begin(); iter != s.end(); iter++) res.push_back(*iter);
        return res;
    }
};

풀이

간단한 투 포인터 문제 입니다.

set을 쓰는 아이디어 정도만 생각해주면 쉽게 풀 수 있습니다.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> s; // 중복을 방지합니다.
        int cnt = 0;
        sort(nums.begin(), nums.end()); // 투 포인터를 사용하기 위하여 nums를 정렬하여 줍니다.
        for (int i = 0; i < nums.size(); i++) {
            int l = i + 1; int r = nums.size() - 1;
            while (l < r) { // 같은 수가 쓰이면 안 되므로 l < r일때 까지만 반복 합니다. 
                if (nums[l] + nums[r] + nums[i] == 0) { // 세 수의 합이 0일 때
                    s.insert({nums[i], nums[l], nums[r]});
                    if (nums[l] == nums[r]) break;
                    l++;
                }
                else if (nums[l] + nums[r] + nums[i] < 0) l++; // 세 수의 합이 0보다 작을 때
                else r--; // 세 수의 합이 0보다 클 
            }
        }
        vector<vector<int>> res;
        for (auto iter = s.begin(); iter != s.end(); iter++) res.push_back(*iter);
        return res;
    }
};
 

 

Input 모두가 0인 경우, 시간초과를 대비하여 다음과 같은 코드를 반복문 안에 넣어줍니다.

 

---

코드 2

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> s;
        int cnt = 0;
        int length = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (j != i + 1 and nums[j] == nums[j - 1]) continue;
                if (binary_search(nums.begin() + j + 1, nums.end(), -nums[i] - nums[j]))
                    if (nums[i] + nums[j] + *lower_bound(nums.begin() + j + 1, nums.end(), -nums[i] - nums[j]) == 0) {
                        s.insert({nums[i], nums[j], *lower_bound(nums.begin() + j + 1, nums.end(), -nums[i] - nums[j])});
                }
            }
        }
        vector<vector<int>> res;
        for (auto& iter: s) res.push_back(iter);
        return res;
    }
};

풀이

이분 탐색으로도 풀 수 있습니다.

Input 모두가 0인 경우, 시간초과를 대비하여 다음과 같은 코드를 반복문 안에 넣어줍니다.