LEETCODE 15. 三数之和
题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
题目地址：
https://leetcode-cn.com/problems/3sum/
题解
这道题的难点是不能包含重复的答案，对于[0,0,0,0,0]这个数组，答案只有一个[0,0,0]。
首先我们对数组先排序一次，在排好序的数组上，就很容判断前后元素是否相当，这样可以过滤掉重复的答案。
再定义三个指针，k，i，j如下图所示
指针i从左往右移动，且始终比k大一位，这样就保证不会跟k重叠，
指针j从右往左移动，且始终比i大，这样i和j就不会重叠，即三个指针都不会重叠。
在这个基础上，实现我们的主要逻辑：
-
nums[k]>0时，可以直接跳出循环，因为nums[k]都比0大了，后面的nums[i]和nums[j]肯定更大，三者加起来肯定大于0 -
nums[k]和nums[k-1]相等，即前后元素重复了，需要过滤掉 -
如果 nums[i]+nums[j]+nums[k]>0，即三者之和太大了，我们将j指针左移，因为三个数中最大的肯定是nums[j]，将j左移就可以减小三者之和。 -
如果 nums[i]+nums[j]+nums[k]<0，说明三者之和太小了，同理将i指针右移 -
如果 nums[i]+nums[j]+nums[k]==0，这就是要找的答案，将其保存起来，同时i右移，j左移 -
i和j在移动的过程中还需要判断前后元素是否重复
时间复杂度：O(n^2):排序O(nlogn)+循环比较O(n^2)
空间复杂度：O(1)
java代码:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if(nums==null) {
return new ArrayList<List<Integer>>();
}
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
int n = nums.length;
//正式处理之前，先将数组排序
Arrays.sort(nums);
//假设数组为[0,1,2,3,4,5,6,7,8,9,10]
//第三个指针k最多到下标8位置，因为后面两个位置需要留给另外两个指针
for(int k=0;k<n-2;k++) {
//nums[k]>0，说明后面的元素肯定也大于0，最后结果肯定>0，故直接跳出
if(nums[k]>0) {
break;
}
//如果当前元素和前面一个元素一样，忽略重复元素
if(k>0 && nums[k-1]==nums[k]) {
continue;
}
//定义另外两个指针 i 和 j
int i = k+1;
int j = n-1;
while(i<j) {
int tmp = nums[i]+nums[j]+nums[k];
//如果三数之和>0，说明最右边的值太大了
if(tmp>0) {
--j;
while(i<j && nums[j+1]==nums[j]) {
--j;
}
}
//如果三数之和<0，说明左边的值太小了
else if(tmp<0) {
++i;
while(i<j && nums[i-1]==nums[i]) {
++i;
}
}
//三数之和等于0，保存结果
//同时左指针往右移动，右指针往左移动，
//如果移动过程中碰到重复元素，则继续移动
else {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[k]);
list.add(nums[i]);
list.add(nums[j]);
res.add(list);
++i;
--j;
while(i<j && nums[i-1]==nums[i]) {
++i;
}
while(i<j && nums[j+1]==nums[j]) {
--j;
}
}
}
}
return res;
}
}
python代码:
class Solution(object):
def threeSum(self, nums):
if not nums:
return []
# 正式处理之前，先将数组排序
nums = sorted(nums)
n = len(nums)
res = []
# 假设数组为[0,1,2,3,4,5,6,7,8,9,10]
# 第三个指针k最多到下标8位置，因为后面两个位置需要留给另外两个指针
for k in xrange(n-2):
# nums[k]>0，说明后面的元素肯定也大于0，最后结果肯定>0，故直接跳出
if nums[k]>0:
break
# 如果当前元素和前面一个元素一样，忽略重复元素
if k>0 and nums[k-1]==nums[k]:
continue
# 定义另外两个指针 i 和 j
i,j = k+1,n-1
while i<j:
tmp = nums[i]+nums[j]+nums[k]
# 如果三数之和>0，说明最右边的值太大了，
if tmp>0:
j -= 1
while i<j and nums[j+1]==nums[j]:
j -= 1
# 如果三数之和<0，说明左边的值太小了
elif tmp<0:
i += 1
while i<j and nums[i-1]==nums[i]:
i += 1
# 三数之和等于0，保存结果
# 同时左指针往右移动，右指针往左移动，
# 如果移动过程中碰到重复元素，则继续移动
else:
res.append([ nums[k],nums[i],nums[j] ])
i += 1
j -= 1
while i<j and nums[i-1]==nums[i]:
i += 1
while i<j and nums[j+1]==nums[j]:
j -= 1
return res
(全文完)
5 次阅读