[LeetCode] 15. 3Sum

Problem

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[1] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

Solution

Approach

1. 배열을 오름차순으로 정렬한다.

2. 첫 요소를 고정 피연산자로 하고, 우측에 남아있는 나머지 배열의 양끝 요소 둘을 또 다른 피연산자로 덧셈을 수행해본다.

3. 덧셈의 결과가 0이 나오면 요소의 집합을 리스트에 추가하고, 두 번째 피연산자를 다음 요소로, 세 번째 피 연산자를 직전 요소로 이동시킨 뒤 덧셈을 수행한다.

4. 합이 0보다 작다면 두 번째 피연산자만 다음 요소이동 시킨 뒤 덧셈을 수행하고, 0보다 크다면 세 번째 피연산자를 직전 요소로 이동 시킨 뒤 덧셈을 수행한다.

5. 고정 피연산자를 다음 요소로 이동 시키며 계산을 수행한다.

Algorithm

Complexity Analysis

• Time Complexity

최악(Worst) : 배열 내 세 요소의 합이 0이 되는 경우가 없을 경우 배열nums의 길이(n)에 따른 while반복문(7)의 실행 횟수는 n - 2 + n - 3 + … + 1 = (n - 2)(n - 1)이 된다. 따라서 O(n²)의 시간 복잡도를 가진다.

평균(Average) : 최악의 경우와 최선의 경우 모두 O(n²)이므로 평균 O(n²)의 시간 복잡도를 가진다.

최선(Best) : 배열 내 세 요소의 합이 모두 0이 되는 경우에는 배열nums의 길이(n)가 홀수일 때, while반복문(7)의 실행 횟수가 (n / 2 - 1) + (n / 2 - 2) + (n / 2 - 2) + … + 1 = (n / 2 - 2)(n / 2 - 1) + n / 2 - 1)이 되고, 짝수일 때, (n / 2 - 1) + (n / 2 - 1) + (n / 2 - 2) + (n / 2 - 2) + … + 1 = (n / 2 - 2)(n / 2)이 되므로 O(n²)의 시간 복잡도를 가진다.

• Space Complexity

최악(Worst) : 배열nums의 길이(n)에 따라 합이 0이 되는 요소의 조합의 개수는 n - 4이다. 따라서 커질 수 있는 Set(3)의 최대 크기는 n - 4가 되고 따라서 O(n)의 공간 복잡도를 가진다.

평균(Average) : 평균적으로는 O(1)의 공간 복잡도를 가지지 못하므로, O(n)의 공간 복잡도를 가진다.

최선(Best) : 합이 0이 되는 요소의 조합이 없거나, 모든 요소의 조합이 0이 되는 경우에는 Set(3)의 크기가 1만큼 할당받으므로, O(1)의 공간 복잡도를 가진다.