DAY 4
5
Software Development

## [Day 4] 從LeetCode學演算法 - 0015. 3Sum (Medium)

``````Question:
Given an array nums of n integers, are there elements a, b, c in numssuch 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]
]
``````

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

Java:

``````class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length-2; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int j = i + 1, k = nums.length - 1, target = 0 - nums[i];
while (j < k) {
if (nums[j] + nums[k] == target) {
while (j < k && nums[j] == nums[j + 1]) j++;
while (j < k && nums[k] == nums[k - 1]) k--;
j++; k--;
} else if (nums[j] + nums[k] < target) ++j;
else --k;
}
}
}
return res;
}
}
``````

Python:
Python的部分提供了另一個的思路，

(對應到Java版本的解法也附在註解處)

``````class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3:
return []
nums.sort()
res = set()
for i, v in enumerate(nums[:-2]):
if i >= 1 and v == nums[i-1]:
continue
d = {}
for x in nums[i+1:]:
if x not in d:
d[-v-x] = 1
else:
return list(res)

'''class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums) - 2):
if i == 0 or (i > 0 and nums[i] != nums[i-1]):
j, k, target = i + 1, len(nums) - 1, 0 - nums[i]
while j < k:
if nums[j] + nums[k] == target:
res.append([nums[i], nums[j], nums[k]])
while j < k and nums[j] == nums[j+1]:
j += 1
while j < k and nums[k] == nums[k-1]:
k -= 1
j += 1
k -= 1
elif nums[j] + nums[k] < target:
j += 1
else:
k -= 1
return res
'''
``````

「(Python)前面不檢查的話後面你怎麼處理重覆？」(用set)
「假設目標不是0的話？」(方法應該是一樣的)
「(Python)dictionary的部分使用set代替會比較快嗎？」(實測過會變慢XD)
「(Java)如果可以改變input/output的變數形態的話，你會希望改動什麼？」
(改output，因為輸出應該固定會是3元組的組合(長度必然是3)，

0021. Merge Two Sorted Lists (Easy)