apache 多个网站,揭阳网页制作公司,e福州官方网站,wordpress 仿豆瓣标注三数之和
在做这道题之前#xff0c;建议建议先将两数之和做完再做#xff0c;提升更大~ 文章目录 三数之和题目描述算法原理解法一解法二思路如下#xff1a;处理细节问题#xff1a; 代码编写Java代码编写C代码编写 15. 三数之和 - 力扣#xff08;LeetCode#xff0…三数之和
在做这道题之前建议建议先将两数之和做完再做提升更大~ 文章目录 三数之和题目描述算法原理解法一解法二思路如下处理细节问题 代码编写Java代码编写C代码编写 15. 三数之和 - 力扣LeetCode 题目描述
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
**注意**答案中不可以包含重复的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例 2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例 3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示
3 nums.length 3000-105 nums[i] 105
算法原理
解法一
排序暴力枚举利用set去重
时间复杂度O(N^3)
解法二
排序双指针
思路如下 首先先排序 固定一个数字a图中我们将第一个数作为aa0 在a的后面的区间中利用双指针算法快速找到两个数的和等于-a即可 双指针 首先在a后面的区间中的两侧的数中分别定义left right两个指针这里关于left right的移动在下面这篇博客中有详细讲解可以先移步学习之后再来做这道题~
处理细节问题
去重要避免越界 找到一种结果的时候left right指针都要跳过重复的元素当使用完一次双指针之后i也需要跳过重复的元素 不漏 在区间中寻找到一种结果之后不能停止继续缩小区间寻找直至区间寻找完全。 代码编写
Java代码编写
class Solution {public ListListInteger threeSum(int[] nums) {// 建立一个线性表存储答案ListListInteger ret new ArrayList();// 1. 排序Arrays.sort(nums);// 2. 双指针解决问题int n nums.length;// 固定数 afor(int i 0; i n; ){// 双指针int left i 1, right n - 1, target -nums[i];while(left right){int sum nums[left] nums[right];if(sum target) right--;else if(sum target) left;else{ret.add(new ArrayListInteger(Arrays.asList(nums[i], nums[left], nums[right])));// 在最小区间继续寻找left; right--;// 去重 left、 rightwhile(left right nums[left] nums[left - 1])left;while(left right nums[right] nums[right 1])right--;}}// 去重 ii;while(i n nums[i] nums[i - 1])i;}return ret;}
}C代码编写
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;// 1. 排序sort(nums.begin(), nums.end());// 2. 利⽤双指针解决问题int n nums.size();for (int i 0; i n; ) // 固定数 a{if (nums[i] 0) break; // ⼩优化int left i 1, right n - 1, target -nums[i];while (left right){int sum nums[left] nums[right];if (sum target) right--;else if (sum target) left;else{ret.push_back({ nums[i], nums[left], nums[right] });left, right--;// 去重操作 left 和 rightwhile (left right nums[left] nums[left - 1]) left;while (left right nums[right] nums[right 1])right--;}}// 去重 i i;while (i n nums[i] nums[i - 1]) i;}return ret;}
};
