Leet code - 3Sum

문제

배열이 주어진다. 3수의 합이 0이 되는 SubArray의 List를 구하여라.

라는 문제고, SubArray는 중복이 있으면 안된다.

해결방법

음 for 문안에 2Sum 문제로 두면 해결할 수 있을 것 같았다.
그러면 시간 복잡도를 $O(n^3)$ 에서 $O(n^2)$으로 줄일 수 있을꺼라 생각했다.

그러나,, 시간 복잡도를 통과 하지 못했다.

아무래도 SubArray간의 중복체크 과정에서 error가 발생하는 모양이다.
따라서 HashSet을 사용하여 시간을 단축했다.

코드

import java.util.*;

class Solution {
    
    
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        HashMap<Integer,Integer> map= new HashMap<>();
        HashSet<List<Integer>> set= new HashSet();

        for(int i=0; i<nums.length-1; i++){
            int sum = nums[i]*(-1);
            map.clear();
            for(int j=i+1; j<nums.length;j++){
                
                if(map.containsKey(sum-nums[j])){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(sum-nums[j]);
                    list.add(nums[j]);
                    Collections.sort(list);
                    set.add(list);
                }
                else map.put(nums[j],j);
            }
        }
        answer = new ArrayList(set);
        
        return answer;
    }
}

결과

시간 복잡도가 처참하다...ㅋㅋ

좀 더 빠르게 풀 수 있는 방법을 찾아 봐야 할 것 같다.