[리트코드] 15. 3Sum

문제

https://leetcode.com/problems/3sum/
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 이 되는 리스트를 구하시오.

풀이

처음에 단순하게 드는 생각은 O ( n^3 ) 으로 for문 3개를 돌려서 중복없이 a + b + c = 0 이 되는 경우를 찾는 것이다. 하지만 속도가 느려 비효율적이다. O(n^2)로 쓸수있는 방법을 생각해보자. 투포인터를 떠올린다면 시간복잡도를 개선할 수 있다.
우리가 찾는 경우는 Sum ( a + b + c ) == 0 인 경우이다. 이 Sum 은 음수, 양수, 0 3가지 case를 가진다. Sum을 구하기 위해 우선 for문을 하나 써서 a값을 가지게 한다. 나머지 b, c는 투포인터로 접근할 것이다.
Sum > 0 일때 Sum의 값을 작게 해줘야하고,Sum < 0 일때 크게 만들어 줘야할 것이다. 이때 정렬을 사용한다. 자바 정렬은 O(nlogn) 임으로 지장없이 사용할 수 있다.

sorted_list = [ -5, -5, -3, -2, 0, 0, 1, 2, 3, 5] 

를 예로 들어보겠다. 여기서 sorted_list[a] = -5,
b = a+1, c = sorted_list.length -1 으로 초기화 해준다. b와 c 투포인터를 사용하여 루프를 돈다.

• Sum > 0 이면 b, c중 큰 값인 sorted_list[c] 의 값을 줄여야 함으로 c-- 를,

• Sum < 0 이면 b, c작은 값인 sorted_list[b]의 값을 커지게 해야함으로 b++를

• Sum == 0 이면 b 와 c 일때 검사가 끝났으니 모두 증감을 해준다. b++, c--

  단 루프를 돌면서 중복 없이 집어넣어야함으로 중복 처리를 해준다.
  이렇게 for문, 투포인터로 시간복잡도는 O(n^2)로 풀수있다.

코드

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        Arrays.sort(nums);//오름차순 정렬
        List<List<Integer>> list = new ArrayList<>();
        
        int l, r;
        for(int i = 0 ; i< nums.length && nums[i] <= 0 ; i++){
            while(i>0 && nums[i] == nums[i-1] &&i+1<nums.length)i++;//중복을 피한다.
            
            l = i+1; 
            r = nums.length-1; 
            while(l < r ){ //투포인터 
                int sum = nums[i]+nums[l]+nums[r];
                if(sum > 0)
                    r--;
             else if(sum < 0)
                      l++;
                        else//when sum == 0 
                        {
                         list.add(Arrays.asList(new Integer[] {nums[i],nums[l],nums[r]} ))   ;
                            l++;
                            r--;
                            while(l < r && nums[l] == nums[l-1])
                                l++;//반복을 없앱니다. 
                            while(l < r && nums[r] == nums[r+1])
                                r--;//반복을 없앱니다. 
                         }
                  }
        }    
        return list;
    }
}