算法题丨3Sum
2024-08-28 02:39:45
描述
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).
附录
最新文章
- 最全面的常用正则表达式大全 zz
- printf的题目
- RequireJS实例分析【转】
- PHP查看SSL证书信息
- javaSE之如何将一个文件复制到另一个文件
- 关于margin和padding的总结
- SharePoint 2013+ Sqlserver 2014 Kerberos 配置传奇, 最终的解决方案 验证。
- value must be omitted for boolean attributes
- 27个Jupyter快捷键、技巧(原英文版)
- FTP链接mac
- iOS字体 UIFont 字体名字大全
- 定制自己的vue模版
- C++ 中memset 勿要对类使用
- Python中and(逻辑与)计算法则
- 如何使用门罗币远程节点remote node?
- IE外挂
- Redis主从+读写分离中可以在从机读取到过期数据
- LeetCode算法题-Missing Number(Java实现-四种解法)
- postgresql-分页重复数据探索
- MVC源码学习之AuthorizeAttribute
热门文章
- Error:Error converting bytecode to dex: Cause: com.android.dex.DexException: Multiple dex files define Lcom/google/android/gms/internal/adp;
- Windows下Python环境的搭建
- createjs绘制扇形的方法
- css学习の第五弹—单位和值
- OpenStack Paste.ini详解(二)
- Lintcode221 Add Two Numbers II solution 题解
- face landmark 人脸特征点检测
- python 全栈开发,Day2(正式)
- 深入剖析Nodejs的异步IO
- Docker学习笔记(一)