LeetCode 15.3Sum

세 수의 합 링크

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.

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

입력: nums = [-1, 0, 1, 2, -1, -5]

출력: [[-1, 0, 1], [-1, -1, 2]]

 

 해당 문제는 Brute force방법으로 O(n^3)에 답을 찾을 수 있으나, O(n^2)만에도 답을 낼 수 있다.

투 포인터 합 계산을 이용해 답을 도출한다. 배열을 정렬한 다음 중복된 값을 건너띄게 하고 투포인터로 풀이한다.

배열을 정렬하면, [-5, -1, -1, 0, 1, 2]가 된다. 예를들어, i = 1일 때 left는 i + 1이고 right는 nums.length - 1이 된다.

nums[i] + nums[left] + nums[right] 세 수의 합이 0보다 크거나 작은 경우에 따라 포인터(left or right)를 조정한다.

left = i + 1;
right = nums.length - 1;

while (left < right) {
    sum = nums[i] + nums[left] + nums[right];
    // ... 생략
}

if (sum < 0) { 
    left += 1;
} else if (sum > 0) {
    right -= 1;
}

 

 sum이 0 이면 정답이므로, 이 경우 결과를 리스트 변수에 추가한다. (List 변수의 명칭은 result로 선언한다.)

추가한 다음에는 left, right 양 옆으로 동일한 값이 있을 수 있으므로 같은 정답이 두 번 나오지 않도록 left += 1, right -= 1 을 반복해서 스킵한다. 마지막으로 left, right를 한칸씩 더 이동한 후 다음으로 넘긴다.

public List<List<Integer>> threeSum(int[] nums) {
    int left, right, sum;
    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;
						
        left = i + 1;
        right = nums.length - 1;
		while (left < right) {
		    sum = nums[i] + nums[left] + nums[right];
						
    		// 합이 0보다 작다면 왼쪽 포인터 이동
	    	if (sum < 0) {
		        left += 1;
                // 합이 0ㅌ보다 크다면 오른쪽 포인터 이동
	    	} else if (sum > 0) {
	    	    right -= 1;
	    	} else {
	    	    // 합이 0인 경우이므로 정답 처리						
	    		result.add(Arrays.asList(nums[i], nums[left], nums[right]));
							
	    		// 중복된 값 건너뛰기, 이 처리를 하지 않으면 같은 정답이 두번 나올 수 있음.
	    		while (left < right && nums[left] == nums[left + 1])
		    	    left += 1;
                    
		    	while (left < right && nums[right] == nums[right - 1])
                    right -= 1;
									
		    	// 정답 이후에는 포인터를 한칸씩 이동함.
		    	left += 1;
			    right -= 1; 
			}
		}
	}
    return result;
}