[LeetCode#15] 3Sum

 

❐ Description

---

문제 링크	https://leetcode.com/problems/3sum/description/
난이도	Medium(골드Ⅴ~Ⅲ)

 

 

 

 

 

❐ 문제 분석

---

주어진 `nums[]`에서 서로 다른 세 수의 합이 0이 되는 조합을 찾아야 한다.

 

 

🧩 Step 1. Two Pointer를 사용하기

세 숫자의 합을 찾는 대신, 첫 번째 숫자를 기준으로 나머지 두 숫자를 Two-Pointer 방식으로 탐색한다.

 

🧩 Step 2. 주어진 nums[] 정렬하기

배열을 오름차순으로 정렬해준다. 이는 Two Pointer 방식을 효율적으로 사용하기 위함이다. 

 

🧩 Step 3. 중복 방지하기

같은 숫자가 여러 번 사용되면 결과에 중복된 조합이 포함되므로 이를 방지해야 한다.

같은 숫자를 연속적으로 사용할 경우 이를 건너 뛰는 로직이 필요하다.

 

 

 

 

 

❐ 문제 풀이

---

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    int left, right, total;
    
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1] {
            continue;
        }
        
        while (left < right) {
            total = nums[i] + nums[left] + nums[right];
            if (total > 0) rigiht--;
            if (total < 0) left++;
            if (total == 0) {
                res.add(List.of(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;
}

 

 

 

 

 

---