[LeetCode] 015. 3Sum JAVA

---

📍 문제

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.

정수 배열 nums가 주어지면 i != j, i != k, j != k
nums[i] + nums[j] + nums[k] == 0.

조금 더 설명을 하자면, 정수 배열인 nums가 주어지면 인덱스가 다른 세 수의 합이 0이 되면 해당 숫자들을 리스트에 담고

그 리스트를 다시 리스트에 담아서 리턴시키면 되는 문제이다.

---

📍 예시

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = [0,1,1]
Output: []

Input: nums = [0,0,0]
Output: [[0,0,0]]

---

📍 풀이 설명

• 결과를 반환할 리스트를 만들어 주었다.
• 숫자들 계산에 편리함을 위하여 배열을 정렬해주었다.
• 세 값의 합이기 때문에 반복문을 사용해주기로 결정하였다.
• 우선 첫 번째 인덱스 값을 지정하기 위한 반복문을 만들어 주고, 그 안에서 while문을 사용하여 세 수를 구하였다.

 

public static List<List<Integer>> threeSum(int[] nums) {

   List<List<Integer>> result = new ArrayList<>();

   Arrays.sort(nums);

   for (int i = 0; i < nums.length - 2; i++) {
  
   }

   return result;
}

---

• 만약 i와 이전의 인덱스의 합이 0이면, 세 수의 합이 0이 될 수 없기 때문에 continue를 사용해 다음 반복문으로 넘겨주었다.
• 두 번째와 세 번째 값을 찾기 위해 두 변수를 만들어 주었다.
• 세 인덱스 값이 다르므로, left는 i의 다음부터 right는 배열의 뒤로 설정해주었다.
• 그리고 다시 반복문을 열어주었다.
• 만약 세 인덱스의 값의 합이 0이면, 리스트에 더하고, 그 리스트를 result 리스트에 더해주었다.
• 그리고 인덱스의 값을 이동시켜주었다.
• 만약 옮긴 인덱스의 배열의 값과 옮기기 전의 배열의 값이 같으면 한 번 더 이동시켜주었다.
• 옮기지 않으면 중복된 값이 저장될 수 있기 때문이다.
• 만약 더한 값이 0보다 크면 뒤에서부터 확인하는 right의 값을 마이너스 시켜주고, 그게 아니라면 left의 값을 플러스해주었다.
• 그리고 결과값을 반환해주었다.

 

public static List<List<Integer>> threeSum(int[] nums) {

   ...

   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;

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

         if (sum == 0) {
            result.add(Arrays.asList(nums[i], nums[left], nums[right]));
            left++;
            right--;
            while (nums[left] == nums[left - 1] && left < right) left++;
            while (nums[right] == nums[right + 1] && left < right) right--;
         } else if (sum > 0) {
            right--;
         } else {
            left++;
         }
      }
   }

   return result;
}

✔️ 이 문제는 세 인덱스가 다르기 때문에, 하나의 인덱스를 고정 시키고 다른 두 인덱스를 이동시키면서 비교해야하는 문제였다.

---

📍 최종 풀이

 

public static List<List<Integer>> threeSum(int[] nums) {

   List<List<Integer>> result = new ArrayList<>();

   Arrays.sort(nums);

   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;

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

         if (sum == 0) {
            result.add(Arrays.asList(nums[i], nums[left], nums[right]));
            left++;
            right--;
            while (nums[left] == nums[left - 1] && left < right) left++;
            while (nums[right] == nums[right + 1] && left < right) right--;
         } else if (sum > 0) {
            right--;
         } else {
            left++;
         }
      }
   }

   return result;
}​

---