dw做的网站怎样才有域名,郑州网站建设q.479185700棒,pdf转wordpress,地域性旅游网站建设系统结构个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣算法分析3️⃣代码编写 1️⃣题目描述
给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 a b c 使得 a b c 0 请找出所有和为 0 且 不重复 的三元组。
示例1 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 示例2 输入nums [] 输出[] 示例3 输入nums [0] 输出[] 注意
0 nums.length 3000-105 nums[i] 105
2️⃣算法分析
本题目可以使用双指针和单调性(排序)的思路来进行操作。具体思路如下
首先使用sort函数对输入的数组进行升序排序这样可以使得相同的数字相邻。然后使用循环遍历数组中的每个数。在循环中定义两个指针l和r分别指向当前数字后面的第一个数和数组的最后一个数。同时定义一个目标值target等于当前数的相反数。这样我们要找的三个数就可以转化为两个数的和等于目标值target的问题。在内层循环中首先根据双指针指向的数的和和target的大小关系进行双指针的移动如果和等于target则找到了一个满足条件的三元组将其添加到结果数组ret中并同时移动左指针l向右和右指针r向左。在移动指针之后为了避免重复的结果需要跳过相邻的相同数。具体做法是如果左指针l指向的数与前一个数相同就继续向右移动指针直到找到一个不同的数为止。同样的在移动右指针r之后如果右指针r指向的数与后一个数相同就继续向左移动指针直到找到一个不同的数为止。在移动指针之后为了避免重复的结果需要跳过相邻的相同数。具体做法是如果左指针l指向的数与前一个数相同就继续向右移动指针直到找到一个不同的数为止。同样的在移动右指针r之后如果右指针r指向的数与后一个数相同就继续向左移动指针直到找到一个不同的数为止。
需要注意的是一定要注意双指针交错的情况
3️⃣代码编写
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint ret;int n nums.size();for(int i 0;i n;){int l i 1, r n - 1, target -nums[i];while(l r){if(nums[l] nums[r] target) r--;else if(nums[l] nums[r] target) l;else{ret.push_back({nums[i],nums[l],nums[r]});l,r--;while(l r nums[l] nums[l - 1]) l;while(l r nums[r] nums[r 1]) r--;}}i;while(i n nums[i] nums[i - 1]) i; }return ret;}
};通过啦
