算法题丨3Sum

描述

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.

示例

Given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

算法分析

难度：中
分析：要求给定的数组，找出满足条件的3个元素组合，使得3个元素之和等于零。注意，元素不能重复(值可以相同)。
思路：首先，我们需要对数组进行排序，比如数组排序后变为[-4, -1, -1, 0, 1, 2]，我们判断第一个元素-4，判断它之后是否有2个元素的和等于4，如果有的话满足条件。因为数组已经排序，只要向当前元素之后查找即可，不用往前查找；
接下来，我们开始遍历排序后的数组，假设当前元素是x，判断本次遍历有解的条件可以转化为找到当前元素之后2个元素和，应该等于0-x，使用夹逼查找方法，检查是否有解，如果有，增加到返回队列，没有的话，进入下一次的遍历，直至找到所有满足条件组合。

代码示例(C#)

public IList<IList<int>> ThreeSum(int[] nums) { //排序 Array.Sort(nums); var res = new List<IList<int>>(); //当前元素向后匹配2个元素，所以最后2个元素不用被遍历 for (int i = 0; i < nums.Length - 2; i++) { if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) { int lo = i + 1, hi = nums.Length - 1, sum = 0 - nums[i]; while (lo < hi) { //找到满足条件元素，添加到返回结果队列 if (nums[lo] + nums[hi] == sum) { res.Add(new List<int> { nums[i], nums[lo], nums[hi] }); //防止重复元素 while (lo < hi && nums[lo] == nums[lo + 1]) lo++; while (lo < hi && nums[hi] == nums[hi - 1]) hi--; //夹逼查找 lo++; hi--; } else if (nums[lo] + nums[hi] < sum) lo++; else hi--; } } } return res; } 

复杂度

• 时间复杂度：O (n²).
• 空间复杂度：O (1).

附录

• 系列目录索引
• 代码实现(C#版)
• 相关算法
  • Two Sum
  • 3Sum Closest
  • 4Sum

文章作者：原子蛋
文章出处：https://www.cnblogs.com/lizzie-xhu/
个人网站：https://www.lancel0t.cn/
个人博客：https://blog.lancel0t.cn/
微信公众号：原子蛋Live+
扫一扫左侧的二维码（或者长按识别二维码），关注本人微信公共号，获取更多资源。
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。