[Dart] 15. 3Sum

1. 문제

https://leetcode.com/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150

 

 

2. 요구사항

1) 정수배열 nums가 주어질 때, 총합이 0이 되는 모든 고유한 세 숫자의 조합을 찾아야 한다.

2) 각 조합은 nums[i] + nums[j] + nums[k] == 0을 만족해야 한다.

3) 결과에는 중복된 조합이 포함되지 않아야 한다.

 

 

3. 코드

class Solution {
  List<List<int>> threeSum(List<int> nums) {
    // nums를 오름차순으로 정렬
    nums.sort();

    List<List<int>> list = [];

    // 첫 번째 숫자를 기준으로 반복
    // 세 수를 찾기 위해 최대 nums.length - 2까지만 반복
    for (int i = 0; i < nums.length - 2; i++) {

      // 중복된 값은 건너뜀
      // 이미 같은 값으로 처리했기 때문
      if (i > 0 && nums[i] == nums[i - 1]) continue;

      int left = i + 1; // 왼쪽 포인터
      int right = nums.length - 1; // 오른쪽 포인터
      int target = -nums[i]; // 두 수의 합이 되어야 하는 값

      while (left < right) {
        int sum = nums[right] + nums[left];

        if (sum == target) {
          // 세 수의 합이 0이면 결과 리스트에 추가
          list.add([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--;
        } else if (sum < target) {
          // 합이 작으면 왼쪽 포인터를 오른쪽으로 이동
          left++;
        } else {
          // 합이 크면 오른쪽 포인터를 왼쪽으로 이동
          right--;
        }
      }
    }

    return list;
  }
}