LEETCODE 15. 三数之和

LEETCODE 15. 三数之和

题目描述

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 abc ,使得 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]
首先我们对数组先排序一次,在排好序的数组上,就很容判断前后元素是否相当,这样可以过滤掉重复的答案。
再定义三个指针,kij如下图所示

指针i从左往右移动,且始终比k大一位,这样就保证不会跟k重叠,
指针j从右往左移动,且始终比i大,这样ij就不会重叠,即三个指针都不会重叠。
在这个基础上,实现我们的主要逻辑:

  • 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左移
  • ij在移动的过程中还需要判断前后元素是否重复

时间复杂度: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 次阅读

发表评论

电子邮件地址不会被公开。