📍 문제
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;
}
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] 016. 3Sum Closest JAVA (0) | 2023.01.05 |
---|---|
[LeetCode] 014.Longest Common Prefix JAVA (0) | 2023.01.04 |
[LeetCode] 013. Roman to Integer JAVA (0) | 2022.12.30 |
[LeetCode] 011.Container With Most Water JAVA (0) | 2022.12.26 |
[LeetCode] 012. Integer to Roman JAVA (0) | 2022.12.23 |
댓글