18. 4Sum

문제

 

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

 

Example 1:

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

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

 

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

 

 

 

 

https://leetcode.com/problems/4sum

 

 

 

풀이

이전에 풀었던 3Sum에서 숫자 1개를 더 선택하는 것으로, 이와 유사하게 풀었다.

배열을 오름차순으로 정렬 후 2개를 미리 선택해 놓고, 나머지 2개에 대해 각 숫자들을 더한 값을 target과 비교하여 target보다 작은 경우 왼쪽 index 증가 / target보다 큰 경우 오른쪽 index 감소를 진행하며 target과 동일한 값이 선택될 때까지 비교했다.

 

한가지 문제였던 점은 주어지는 배열 내 숫자가 10억이라 4개를 선택하는 경우 합이 최대 40억이 될 수 있었고, 이는 int의 양수/음수 최대값인 2,147,483,647을 넘는 문제가 있었다.

이에 선택한 4개의 합은 int보다 큰 자리수 표현이 가능한 long으로 계산하도록 진행하여 완료했다.

 

코드

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        HashSet<List<Integer>> res = new HashSet<>();
    	
    	Arrays.sort(nums);
    	
    	for(int i = 0; i < nums.length-3; i++) {
    		for(int j = i+1; j < nums.length-2; j++) {    			
    			int left = j + 1;
    			int right = nums.length - 1;
    			while(left < right) {
    				long temp_target = Long.valueOf(nums[left]) + Long.valueOf(nums[right]) + Long.valueOf(nums[i]) + Long.valueOf(nums[j]);    				
    				if (temp_target < target) {
    					left++;
    				} else if (temp_target == target) {
    					List<Integer> res_temp = new ArrayList<>();
    					res_temp.add(nums[i]);
    					res_temp.add(nums[j]);
    					res_temp.add(nums[left]);
    					res_temp.add(nums[right]);
    					res.add(res_temp);
    					left++;
    					right--;
    				} else {
    					right--;
    				}
    			}
    		}

    	}
    	return new ArrayList<>(res);
    }
}

 

 

결과

Runtime : 143 ms

Memory Usage : 45.54 MB