征二级网站建设意见 通知,招商外包公司,系统搭建流程,上海市工程建设信息网官方网站文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;暴力枚举方法二#xff1a;双指针 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对… 文章目录 写在前面Tag题目来源题目解读解题思路方法一暴力枚举方法二双指针 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【双指针】【数组】 题目来源
面试经典150 | 15. 三数之和 题目解读
给你一个整数数组 nums找出其中所有同时满足以下条件的三元组
nums[i] nums[j] nums[k] 0i ! j、j ! k 且 k ! i
注意答案中不允许包含重复的三元组。 解题思路
方法一暴力枚举
找出和为 0 的三元组最容易想到的方法就是枚举所有可能的三元组然后求和。但是答案中不允许包含重复的三元组因此想到先进行排序处理将数组 nums 中所有重复的元素放在一起方便后续的去重处理这一步也是后续几种方法的必要的步骤。
枚举所有可能的三元组的方法最容易想到但是时间复杂度为 O ( n 3 ) O(n^3) O(n3) n n n 为数组 nums 的长度本题的数据量达到 1 0 3 10^3 103必然超时。
方法二双指针
为了应对重复答案的情况出现我们首先对数组 nums 进行排序处理。
接着枚举第一个加数 nums[i]剩下两个加数的查找我们可以使用 两数之和 中双指针的思想来解决具体地
枚举第一个加数 nums[i]如果 i 1 且 nums[i] nums[i-1]说明数字 nums[i] 已经作为第一个元素了 我们需要则继续枚举下一个位置的 nums[i] 作为第一个加数否则利用双指针查找第二、三个加数维护双指针 j、k 分别指向需要查找的第二、三个数字位置初始化 j i 1、k n - 1如果 nums[i] nums[j] nums[k] 0则 --k如果 nums[i] nums[j] nums[k] 0则 j如果 nums[i] nums[j] nums[k] 0则当前的 {nums[i], nums[j], nums[k]} 为一个满足条件的三元组并加入到 答案数组 ret 中并且右移 j 到下一个与数字 nums[j] 的位置左移 k 到下一个与数字 nums[k] 的位置 。
最后返回答案数组 ret。
优化
本题中还有一些可以优化的地方
如果 n 3即数组的长度小于 3不会有三个数如果排序后的 nums[0] 0表明数组中的所有数字都大于 0一定不会有和为 0 的三元组如果排序后的 nums[n-1] 0表明数组中的所有数字都小于 0一定不会有和为 0 的三元组
加上以上的优化代码双指针解法就是最优的解法了。
实现代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;int n nums.size();sort(nums.begin(), nums.end());if(n 3 || nums[0] 0 || nums[n-1] 0){return ret;}int i, j, k;for(i 0; i n-2; i){if(i nums[i] nums[i-1]){continue;}j i 1;k n - 1;while(j k){int target nums[i] nums[j] nums[k];if(target 0){--k;}else if(target 0){j;}else{ret.push_back({nums[i], nums[j], nums[k]});j;--k;while(j k nums[j] nums[j-1]) j;while(j k nums[k] nums[k 1]) --k;}}}return ret;}
};复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2) n n n 为数组 nums 的长度枚举第一个加数的时间复杂度为 O ( n ) O(n) O(n)利用双指针查找满足条件的第二、三个加数的时间复杂度为 O ( n ) O(n) O(n)因此总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
空间复杂度 O ( l o g n ) O(logn) O(logn)双指针解法仅使用有限个额外空间排序占用的额外空间为 O ( l o g n ) O(logn) O(logn)因此空间复杂度为 O ( l o g n ) O(logn) O(logn)。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
