[LeetCode#15] 3Sum

❒ Description

---

 

제목	3Sum
링크	https://leetcode.com/problems/3sum/description/
자료구조	선형 자료구조
시간복잡도	Two Pointer 풀이 - O(n²)

 

선형 자료구조 문제로, two pointer 알고리즘을 사용하여 해결할 수 있는 문제.

이 문제는 중복 값에 대한 적절한 처리를 해줘야 하는 점이 까다로웠다.

 

❒ Solution

---

public static List<List<Integer>> solve(int[] nums) {
    int left, right, total;
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length -2; i++) {
        // 중복된 값 건너뛰기
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        left = i + 1;
        right = nums.length - 1;
        while (left < right) {
            total = nums[i] + nums[left] + nums[right];
            if (total > 0) {
                right --;
            } else if (total < 0) {
                left ++;
            } else {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 중복된 값 건너 뛰기, 이 처리를 하지 않으면 같은 정답이 주번 나올 수 있다.
                while (left < right && nums[left] == nums[left + 1]) {
                    left ++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right --;
                }
                left ++;
                right --;
            }
        }
    }
    return res;
}

 

이 문제는 Two Pointer 알고리즘을 통해서 해결할 수 있다.

1. 중복 값 예외 작업을 해준다.
2. 우선 Two Pointer 알고리즘을 위해 nums를 정렬해준다.
3. left와 right pointer를 설정해준다.
4. 각 pointer를 조건에 따라 이동 시킨다.
   • 여기서는 합이 0보다 작을 경우 left pointer를, 0 보다 클 경우에는 right pointer를 이동시킨다.
5. 중복갑 예외 작업을 해준다.
6. 원하는 결과가 나온경우 left, right pointer를 각각 한 칸씩 이동한다.

---

그리고 위 코드의 시간 복잡도는 O(n²) 이다.

• 입력 받은 배열을 정렬하는데 O(nlogn)
• for문과 while문이 중첩으로 있기 때문에 O(n²)