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
(全文完)
16 次阅读