3sum

CREATED TIME: Dec 24, 2019 1:20 AM UPDATED TIME: Dec 25, 2019 11:34 PM 난이도: Medium

접근한 풀이법들

• n^2 + hash_map
  • n^2으로 쌍을 묶고, 0-해당값 에 해당하는 value가 존재하는지 체크
  • 하지만 결과에 대한 중복을 다시 한번 처리해줘야함.
  • 소팅을 해야겠다는 생각이 듬.
• two pointer
  • 소팅을 하고
  • 가장 작은 값을 고정해두고
  • 두 포인터를 범위 내 가장 큰값, 가장 작은값으로 설정.
    • 범위는 가장 작은값을 설정한 index+1 부터.
  • 투포인터로 합이 0이되는지점 찾기
  • [-1, 0, 0, 1, 1] 같이 같은 값이 중복될 경우가 존재.
    • 따라서 합이 0이 된 경우 똑같은 값을 넘어가도록 한번 더 반복을 넣어줌.

  class Solution { public: vector<vector> threeSum(vector& nums) { vector<vector> res;

        if (nums.empty()){
            return res;
        }
        sort(nums.begin(), nums.end());
        int length = nums.size();        
          
          
        for(int i = 0; i < length - 2; i++){
            if(i == 0 || nums[i] != nums[i-1]){
                int left = i+1;
                int right = length-1;
                while(left < right){
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum == 0){
                        vector<int> vc{nums[i], nums[left], nums[right]};
                        res.push_back(vc);
                        while(left < right && nums[left] == nums[left + 1] && nums[right] == nums[right - 1]){
                            left++;
                            right--;
                        }
                        left++;
                        right--;
                    }else if(sum > 0){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
        }
        return res;
    }   };