[LeetCode] 15. 3Sum

https://leetcode.com/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150 

3Sum - LeetCode

문제 유형 : 투 포인터

문제 난이도 : Medium

 

문제

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 

세 수의 합이 0이 되는 쌍을 모두 찾아 반환하시오. 중복이 존재하면 안됩니다.

 

풀이

배열을 정렬하고, i는 0부터 n-1까지 돌아간다.

j와 k는 각각 i+1과 n-1부터 시작해서 투 포인터 연산으로 조합을 찾는다.

한 i에서 여러 조합이 생길 수 있으므로 0을 만드는 조합을 찾아도 리스트에 추가만 하고, 탐색을 중단하지는 않는다.

중복을 피하기 위해서 집합에 조합을 담고, 마지막에 2차원 배열에 넣어서 반환시킨다.

 

코드

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        const int target = 0;
        const int n = nums.size();
        sort(nums.begin(), nums.end());

        set<vector<int>> s;
        vector<vector<int>> output;
        for(int i = 0; i < n; i++) {
            int j = i+1;
            int k = n-1;

            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == target) {
                    s.insert({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }

        for(auto triplets : s) {
            output.push_back(triplets);
        }
        return output;
    }
};

 

Python3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        target = 0
        n = len(nums)
        nums.sort()
        s = set()

        for i in range(n):
            j = i+1
            k = n-1
            while j < k:
                _sum = nums[i] + nums[j] + nums[k]
                if _sum == target:
                    s.add((nums[i], nums[j], nums[k]))
                    j += 1
                    k -= 1
                elif _sum < target:
                    j += 1
                else:
                    k -= 1
        
        output = [list(item) for item in s]
        return output

 

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int target = 0;
        int n = nums.length;
        Arrays.sort(nums);
        
        Set<List<Integer>> s = new HashSet<>();
        List<List<Integer>> output = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int j = i + 1;
            int k = n - 1;
            
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    s.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        
        output.addAll(s);
        return output;
    }
}