[leetcode] 15. 3 Sum 문제 풀이 보고서

제목 링크:https://leetcode.com/problems/3sum/
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

사고: 방금 시작 한 사고 방향 은 정렬 + DFS 검색 + 역 추적 이 고 시간 복잡 도 는 O (n ^ 3) 이 며 시간 초과 입 니 다.
코드 는 다음 과 같 습 니 다:

class Solution {
public:
    void DFS(vector<int>& nums, vector<int> tem, int index, int sum)
    {
        if(tem.size() == 3)//       ，       
        {
            if(sum == 0)
                result.push_back(tem);
            return;
        }
        if(index >= nums.size() || sum >0) return;
        tem.push_back(nums[index]);
        DFS(nums, tem, index+1, sum+nums[index]);
        while(index+1 < nums.size() && nums[index+1] == nums[index])//     
            index++;
        tem.pop_back();//  
        DFS(nums, tem, index+1, sum);
    }
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        if(len ==0) return result;
        sort(nums.begin(), nums.end());
        vector<int> tem;
        DFS(nums, tem, 0, 0);
        return result;
    }
private:
    vector<vector<int>> result;
};

나중에 다른 사람의 답안 을 다시 보 니 이 문제 가 투 썸 문제 의 해법 으로 퇴화 할 수 있다 는 것 을 알 게 되 었 다.먼저 하나의 숫자 를 골 라 낸 다음 에 나머지 숫자 에서 두 개의 숫자 와 이 수 를 더 하면 0 과 같다 는 것 을 찾 아 문 제 를 2Sum 문제 로 바 꿀 수 있다.
하나의 수 를 target 으로 고 른 후에 이 수 와 관련 된 모든 해 를 찾 을 수 있 기 때문에 앞으로 이 수 를 검색 하지 않 으 면 중복 해 가 있 을 수 있 습 니 다.
밤 들 기: - 10, - 5, - 5, 5, 5, 6, 10
첫 번 째 는 - 10 을 target 으로 하고 - 5, - 5, 5, 5, 6, 10 에서 검색 결 과 를 얻 습 니 다.
두 번 째 는 - 5 를 target 으로 하고 - 5, 5, 5, 6, 10 에서 결 과 를 고 르 세 요.
세 번 째 로 5 를 target 으로, 5, 6, 10 중에서 결 과 를 고 르 는데, 이번 에는 하 나 를 건 너 뛰 었 습 니 다. - 5 를 target 으로 하 는 해 를 찾 았 기 때 문 입 니 다.
응!이렇게 코드 는 다음 과 같 습 니 다.

class Solution {
public:
    void twoSum(vector<int>& nums, int left, int target)
    {
        int right = nums.size() -1;
        while(left < right)
        {
            int value = nums[left] + nums[right] + target;
            if(value == 0)//      
            {
                vector<int> tem;
                tem.push_back(target);
                tem.push_back(nums[left++]);
                tem.push_back(nums[right--]);
                result.push_back(tem);
                while(nums[left] == nums[left-1]) left++;//  
                while(nums[right] == nums[right+1]) right--;//  
            }
            else if(value < 0)
                left++;
            else if(value > 0)
                right--;
        }
    }
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        if(len ==0) return result;
        sort(nums.begin(), nums.end());
        for(int i =0; i< len-1; i++)//        target
        {
            if(i >0 && nums[i] == nums[i-1])
                continue;
            twoSum(nums, i+1, nums[i]);
        }
        return result;
    }
private:
    vector<vector<int>> result;
};

두 번 째 방법 참고:http://www.sigmainfy.com/blog/summary-of-ksum-problems.html
2016 - 02 - 24 재 편집

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size() == 0) return result;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        for(int i = 0; i< len -2; i++)
        {
            int left = i+1, right = len-1;
            while(left < right)
            {
                int val = nums[left] + nums[right] + nums[i];
                if(val ==0)
                {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    while(nums[left] == nums[left+1]) left++;
                    while(nums[right] == nums[right-1]) right--;
                    left++, right--;
                }
                else if(val > 0) right--;
                else left++;
            }
            while(i+1 < len && nums[i] == nums[i+1])
                i++;
        }
        return result;
    }
private:
    vector<vector<int>> result;
};