Day 8

3Sum

문제

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.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

Hint:

1. So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!
2. For the two-sum problem, if we fix one of the numbers, say

   x

, we have to scan the entire array to find the next number

y

which is

value - x

where value is the input parameter. Can we change our array somehow so that this search becomes faster?

3. The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

답(Java)

class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> list = new ArrayList<>();
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 2; ++i) {
			if (nums[i] > 0) break;
		    	if (i == 0 || (i > 0) && (nums[i] != nums[i-1])) {
				int l = i + 1;
				int r = nums.length - 1;
				int sum = -nums[i];
				while (l < r) {
					if (nums[l] + nums[r] == sum) {
						list.add(Arrays.asList(nums[i], nums[l], nums[r]));
						l++;
						r--;
                        			while (l < r && nums[l] == nums[l-1]) l++;
						while (l < r && nums[r] == nums[r+1]) r--;
					}
					else if (nums[l] + nums[r] < sum)
						l++;
					else
						r--;
				}
            		}
		}
	return list;
    }
}

주어진 정수 배열에서 합이 0이 되는 세 정수를 찾는 문제다. 단순하게 풀면 삼중 for loop을 돌면서 합이 0이 되는 세 숫자를 찾을 수 있다. 조금 더 효율적으로 문제를 풀려면 다른 방법을 사용해야 한다.
여기서 사용한 방법은 한 숫자를 고정시키고 나머지 두 숫자를 찾는 방법이다. 먼저 배열을 정렬한다. 맨 처음 요소부터 고정시키고 고정된 숫자를 제외한 양끝에서 부터 합이 0이 되는 나머지 두 숫자를 검색한다. 합이 모자라면 l을 증가시키고 합이 넘치면 r을 감소시켜 합이 0이 되는 세 숫자를 찾는다. 이 때 중복된 숫자는 넘어가도록 별도로 처리해준다.