
问题
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
Given an array nums of n integers, are there elements a, b, c in nums 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.
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
示例
public class Program { public static void Main(string[] args) { var intervals = new int[] { -1, 0, 1, 2, -1, -4 }; var res = ThreeSum(intervals); ShowArray(res); intervals = new int[] { 0, 0, 0 }; res = ThreeSum2(intervals); ShowArray(res); Console.ReadKey(); } private static void ShowArray(IList<IList<int>> list) { foreach(var nums in list) { foreach(var num in nums) { Console.Write($"{num} "); } Console.WriteLine(); } } public static IList<IList<int>> ThreeSum(int[] nums) { //暴力解法肯定超时无法AC var res = new List<IList<int>>(); for(int i = 0; i < nums.Length; i++) { for(int j = 0; j < nums.Length; j++) { for(int k = 0; k < nums.Length; k++) { if(nums[i] + nums[j] + nums[k] == 0 && i != j && j != k && k != i) { var line = new List<int> { nums[i], nums[j], nums[k] }; line = line.OrderBy(r => r).ToList(); if(!res.Any(l => l[0] == line[0] && l[1] == line[1] && l[2] == line[2])) { res.Add(line); } } } } } return res; } public static IList<IList<int>> ThreeSum2(int[] nums) { //先固定 i,再计算三数之和是不是0 //需认真分析是否有重复的三元组 var res = new List<IList<int>>(); var length = nums.Length; Array.Sort(nums); for(var i = 0; i < length - 2; i++) { //定义左右指针j和k //i为循环变量,可以认为先固定了i var j = i + 1; var k = length - 1; //分析j和k while(j < k) { //若和大于0,则需要减整体的值,将右指针 k 减1 if(nums[i] + nums[j] + nums[k] > 0) k--; //若和小于0,则需要加整体的值,将左指针 j 加1 else if(nums[i] + nums[j] + nums[k] < 0) j++; else { //若和正好等于0,将其存放进结果中 //然后需要处理重复三元组的情况 //不重复三元组需要3个索引各不相同并且组成的值的结果不能重复 //以下3个条件组成了满足不重复三元组的所有条件 //条件1:i、j、k的顺序具有稳定性,总是从小到大 res.Add(new int[] { nums[i], nums[j], nums[k] }); //首先使用 j + 1 <= nums.Length - 1 保证数组不越界 //条件2:再向右找到第1个值不和当前左指针相同的值的索引 //若为 1,1,1,1,1,2,找到2 while(j + 1 <= nums.Length - 1 && nums[j + 1] == nums[j++]) { } } } //条件3:向右找到最后1个和当前被固定的 i 的值相同的值的索引 //若为 1,1,1,1,1,2,找到2前面的最后一个1 while(i + 1 <= nums.Length - 1 && nums[i + 1] == nums[i]) i++; } return res; } }
以上给出2种算法实现,以下是这个案例的输出结果:
-1 0 1 -1 -1 2 0 0 0
分析
显而易见, ThreeSum 的时间复杂度为: O(n^3)O(n3),ThreeSum2 的时间复杂度为:O(n^2)O(n2) 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3618。