👀 문제
https://leetcode.com/problems/3sum/
👊 도전
1. 설계
- 숫자별 영어를 char[][]에 저장한다.
- input을 하나씩 확인하며 combination으로 모두 구한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
*
* @author HEESOO
*
*/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
HashSet<List<Integer>> set=new HashSet<>();
for(int i=0;i<nums.length-2;i++){
int j=i+1, k=nums.length-1;
while(j<k){
long sum=nums[i]+nums[j]+nums[k];
if(sum>0) k--;
else if(sum<0) j++;
else {
set.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
}
}
}
return new ArrayList(set);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- i, j, k를 두어 숫자 3개를 선택한다
- nums를 오름차순으로 정렬한다.
- i는 0부터 n(길이)-2까지 가능하다. 끝애서 두 개는 j, k를 위함이다.
- j는 i+1부터 k보다 작은 수까지 이다.
- k는 j보다 크고 n보다 작은 범위다.
- nums[i]+nums[j]+nums[k]가 0 이상이면 가장 큰 수 k를 하나 줄인다.
- 0 이하이면 j를 키운다(i는 고정).
- 0이라면 HashSet에 저장한다. 중복 값을 방지하기 위함이다.