[LeetCode#15] 3Sum

2025. 1. 21. 22:17·Algorithm/문제풀이

 

❐ 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;
}

 

 

 

 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

'Algorithm > 문제풀이' 카테고리의 다른 글

[LeetCode#152] Maximum Product Subarray  (0) 2025.01.16
[LeetCode#300] Longest Increasing Subsequence  (0) 2025.01.15
[LeetCode#151] Reverse Words in a String  (0) 2025.01.13
[LeetCode#198] House Robber  (0) 2025.01.09
[LeetCode#128] Longest Consecutive Sequence  (0) 2025.01.07
'Algorithm/문제풀이' 카테고리의 다른 글
  • [LeetCode#152] Maximum Product Subarray
  • [LeetCode#300] Longest Increasing Subsequence
  • [LeetCode#151] Reverse Words in a String
  • [LeetCode#198] House Robber
gilbert9172
gilbert9172
gilbert9172 님의 블로그 입니다.
  • gilbert9172
    バックエンド
    gilbert9172
  • 전체
    오늘
    어제
    • All Categories (166)
      • 우테코 7기 (21)
        • 1주차 (8)
        • 2주차 (5)
        • 3주차 (6)
      • Langauge (4)
        • Java (3)
        • Kotlin (1)
      • Back-End (13)
        • SpringBoot (1)
        • Trouble Shooting (0)
        • Setup & Configuration (1)
        • SQL (3)
        • Redis (8)
      • Architecture (6)
        • Multi Module (1)
        • DDD (5)
      • CS (30)
        • Data Structure (6)
        • Operating System (0)
        • Network (12)
        • Database (10)
        • Design Pattern (2)
      • Algorithm (78)
        • 내용 정리 (18)
        • 문제풀이 (60)
      • DevOps (6)
        • AWS (5)
        • Git (1)
      • Front-End (1)
        • Trouble Shooting (1)
      • Project (6)
        • 페이스콕 (6)
      • Book (0)
        • 마스터링 블록체인 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    greedy
    sliding-window
    부분단조성
    Two-Pointer
    binarysearch
    오블완
    Back-Tracking
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.2
gilbert9172
[LeetCode#15] 3Sum
상단으로

티스토리툴바