[AlphaGo Study] [LeetCode] [JAVA] 15. 3 Sum

문제 설명

 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

 Notice that the solution set must not contain duplicate triplets.

제한 사항

☞ 0 ≤ nums.length ≤ 3000

☞ -100000 ≤ nums[i] ≤ 100000

입출력 예

Input	Output
[-1, 0, 1, 2, -1, -4]	[-1, -1, 2]	[-1, 0, 1]
[ ]	[ ]
[0]	[ ]

입출력 예 설명

#예제1

-1 + 0 + 1 = 0이고, -1 + (-1) + 2 = 0이므로 두 개의 output이 있다.

 

leetcode.com/problems/3sum/

3Sum - LeetCode

---

문제를 풀기 전 THINK

 § HashSet, TreeSet 등 Set은 사용할 수 없으므로 알고리즘으로만 구현해야함.

 § nums가 비어있거나 더할 숫자가 3개 미만이면 [ ]을 반환.

 § 정렬 꼭! (정렬하여 비교하는 것이 내가 짠 알고리즘의 기반)

 § a + b + c = 0   ⇒ a + b = -c 를 이용하여 sum을 정의.

 § for문은 nums_len의 -2. 하나는 지정해두고 나머지를 비교하기 때문.

 § 중복 제거를 위한 while문 구현.

나의 Solution

public class ThreeSum {
	public static List<List<Integer>> threeSum(int[] nums) {
		int nums_len = nums.length;
		List<List<Integer>> result = new ArrayList<>();
		
		if(nums_len == 0 || nums_len < 3) { return result; }
		
		Arrays.sort(nums);
		
		// 하나는 지정해두고 나머지를 비교하기 때문에 -2
		// ex) [-4, -1, -1, 0, 1, 2] 에서 나는 -4, 그러면 나머지 5개중에서 찾기 시작
		for(int i = 0; i < nums_len - 2; i++) {
			if(i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
				int low = i + 1;
				int high = nums_len - 1;
				
				// a + b + c = 0   ⇒   a + b = -c
				// 나 자신에서 -를 붙인 그 값을 찾으면 됨
				// ex) 내가 3이면, 이제 나머지 두 개를 더해서 -나(= -3)를 하면 결국 나(3) + 나머지2개의합(-3) = 0 이 됨
				int sum = 0 - nums[i]; 
				
				while(low < high) {
					if(nums[low] + nums[high] == sum) {
						result.add(Arrays.asList(nums[i], nums[low], nums[high]));
						// 중복 제거!
						while(low < high && nums[low] == nums[low + 1]) { low++; } // nums[low]가 다음 값과 같으면 다를 때까지 low를 증가
						while(low < high && nums[high] == nums[high - 1]) { high--; } // nums[high]가 전 값과 같으면 다를 때까지 high를 감소
						low++;
						high--;
					} else if(nums[low] + nums[high] > sum) {
						high--;
					} else {
						low++;
					} // if ~ else if ~ else end
				} // while end
			} // if end
		} // for end
		return result;
    }

Comment...

처음에도 알고리즘을 짰는데 완전 갈아엎었다...Leetcode에서 submit했더니 시간초과 ㅡㅡ..돌아가는 건 다 돌아갔음 ㅠ 예시넣고 run code 하는거 ..ㅜ_ㅜ 슬픈 일...근데 Set을 써서 어차피 고치긴 했어야했다

Set<List<Integer>> result = new HashSet<>();
	        int nums_len = nums.length;
	        
	        if(nums_len == 0 || nums_len < 3) { return new ArrayList<>(); }
			
	        Arrays.sort(nums);
	        
	        for(int i = 0; i < nums_len - 1; i++) {
	        	for(int j = i + 1; j < nums_len - 1; j++) {
	        		for(int k = j + 1; k < nums_len; k++) {
	        			if(nums[i] + nums[j] + nums[k] == 0) {
	        				result.add(Arrays.asList(nums[i], nums[j], nums[k]));
	        			} // if end
	        		} // for(k) end
	        	} // for(j) end
	        } // for(i) end
	        return new ArrayList<>(result);