[LeetCode] 15. 3Sum

轉自LeetCode

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

<Solution>

這題是 two sum 的衍生題，比較麻煩一點

首先，暴力解一定是TLE，所以不考慮

然後要注意到 input 的數字有可能重複

例如 [-1, -1, -1, 2, 0, 2, 1, 3, 1]

這題的答案會是 [[-1, -1, 2], [-1, 0, 1]]，因為題目要求不要有 duplicate triplets

那三個數的相加，是比較難處理的

所以先對 input 做排序，從小到大，然後將問題簡化成找 two sum

a + b + c = 0   =>  a + b = 0 - c

因此對排序後的 array，開始歷遍找每個位置是否有對應的 a+b

歷遍的時候要避開重複的數字

code 如下

C++

	class Solution {
	public:
	vector<vector<int>> threeSum(vector<int>& nums) {
	vector<vector<int>> ans;
	//>> sort first
	sort(nums.begin(), nums.end());
	const int len = nums.size();
	const int total = len - 2;
	int target, sum;
	int left, right;
	for(int i = 0; i < total; i++) {
	if(i == 0 || (nums[i] <= 0 && nums[i] != nums[i-1])) {
	//>> change the question to two sum question
	target = -nums[i];
	left = i+1;
	right = len-1;
	while(left < right) {
	sum = nums[left] + nums[right];
	if(sum == target) {
	ans.push_back({nums[i], nums[left++], nums[right--]});
	//>> skip the same ans
	while(left < right && nums[left] == nums[left-1]) {
	++left;
	}
	while(right > left && nums[right] == nums[right+1]) {
	++right;
	}
	}
	else if(sum < target) {
	++left;
	}
	else {
	--right;
	}
	}
	}
	}
	return ans;
	}
	};

view raw threeSum.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> ans = new ArrayList<>();
	//>> sort first
	Arrays.sort(nums);
	int target, sum;
	int left, right;
	final int len = nums.length;
	final int total = len - 2;
	for(int i = 0; i < total; i++) {
	if(i == 0 || (nums[i] <= 0 && nums[i] != nums[i-1])) {
	//>> turn the question into two sum question
	target = -nums[i];
	left = i+1;
	right = len - 1;
	while(left < right) {
	sum = nums[left] + nums[right];
	if(sum == target) {
	ans.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
	//>> skip the same ans
	while(left < right && nums[left] == nums[left-1]) {
	++left;
	}
	while(right > left && nums[right] == nums[right+1]) {
	--right;
	}
	}
	else if(sum < target) {
	++left;
	}
	else {
	--right;
	}
	}
	}
	}
	return ans;
	}
	}

view raw threeSum.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun threeSum(nums: IntArray): List<List<Int>> {
	val ans = mutableListOf<List<Int>>()
	nums.sort()
	var target: Int
	var left: Int
	var right: Int
	var sum: Int
	for(i in nums.indices) {
	if (i == 0 || (nums[i] <= 0 && nums[i] != nums[i-1])) {
	target = -nums[i]
	left = i + 1
	right = nums.lastIndex
	while (left < right) {
	sum = nums[left] + nums[right]
	if (sum == target) {
	ans.add(listOf(nums[i], nums[left++], nums[right--]))
	while (left < right && nums[left] == nums[left-1]) {
	++left
	}
	while (left < right && nums[right] == nums[right+1]) {
	--right
	}
	} else if (sum < target) {
	++left
	} else {
	--right
	}
	}
	}
	}
	return ans
	}
	}

view raw 3Sum.kt hosted with ❤ by GitHub