上哪儿找做网站,直接用ip做网站,杭州网站建设培训班,商场装修设计相信大家都有做过两数之和#xff0c;
题目链接#xff1a; 15. 三数之和 - 力扣#xff08;LeetCode#xff09;
在文章的开始让我们回顾一下三数之和吧#xff01;
题目描述#xff1a;
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], …相信大家都有做过两数之和
题目链接 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 。 解题思路:
首先要使形如a b c 0,我们可以座一层循环让i表示a,通过双指针表示另外两个数left--b,right--c;在动手解题前一定要对数组做预处理排序这样可以避免很多麻烦我们让i从数组下标第一个元素开始left取i 1;right取nums.length - 1;i不动让两个指针移动判断sumabc的值当sum0时证明整体大了需要减小和故使right--;当sum0时证明整体小了需要增大和故使left;sum0即一组解。
整体思路就是这样当其实有很多细节的地方尤其是 去重这也是解本题最关键的地方我们需要对a b c去重避免重复解。
对a去重 if(i0 and nums[i]nums[i-1]) continue;
对b c去重 ifright left and nums[right] nums[right--] ) right--; if (right left and nums[left] nums[left] ) left;
上代码
代码详解可看强推简单易懂细节拉满 梦破碎的地方| LeetCode15.三数之和_哔哩哔哩_bilibili
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();//预处理---》排序Arrays.sort(nums);for(int i0;i nums.length;i){if(nums[i] 0) break; // 对a去重if(i 0 nums[i] nums[i - 1]){continue;}int left i 1;int right nums.length - 1;// 指针移动条件while(right left){int sum nums[i] nums[left] nums[right];if(sum 0){right--;}else if(sum 0){left;}else{// 先收获结果集在去重 确保至少收获一个结果集res.add(Arrays.asList(nums[i],nums[left],nums[right]));// 对b c去重 这里需要移动 不能用if做判断会漏解的****while(right left nums[left] nums[left1]){left;}while(right left nums[right] nums[right-1]){right--;}right--;left;}}}return res;}
}
这里在给出一个版本的参考
如果有朋友实在理解不了的话这里给出一个n数之和的解决方案直接就是背
c版本
class Solution {public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(), nums.end());// n 为 3从 nums[0] 开始计算和为 0 的三元组return nSumTarget(nums, 3, 0, 0);}/* 注意调用这个函数之前一定要先给 nums 排序 */// n 填写想求的是几数之和start 从哪个索引开始计算一般填 0target 填想凑出的目标和vectorvectorint nSumTarget(vectorint nums, int n, int start, int target) {int sz nums.size();vectorvectorint res;// 至少是 2Sum且数组大小不应该小于 nif (n 2 || sz n) return res;// 2Sum 是 base caseif (n 2) {// 双指针那一套操作int lo start, hi sz - 1;while (lo hi) {int sum nums[lo] nums[hi];int left nums[lo], right nums[hi];if (sum target) {while (lo hi nums[lo] left) lo;} else if (sum target) {while (lo hi nums[hi] right) hi--;} else {res.push_back({left, right});while (lo hi nums[lo] left) lo;while (lo hi nums[hi] right) hi--;}}} else {// n 2 时递归计算 (n-1)Sum 的结果for (int i start; i sz; i) {vectorvectorintsub nSumTarget(nums, n - 1, i 1, target - nums[i]);for (vectorint arr : sub) {// (n-1)Sum 加上 nums[i] 就是 nSumarr.push_back(nums[i]);res.push_back(arr);}while (i sz - 1 nums[i] nums[i 1]) i;}}return res;}
};java版本
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);// n 为 3从 nums[0] 开始计算和为 0 的三元组return nSumTarget(nums, 3, 0, 0);}/* 注意调用这个函数之前一定要先给 nums 排序 */// n 填写想求的是几数之和start 从哪个索引开始计算一般填 0target 填想凑出的目标和public ListListInteger nSumTarget(int[] nums, int n, int start, int target) {int sz nums.length;ListListInteger res new ArrayList();// 至少是 2Sum且数组大小不应该小于 nif (n 2 || sz n) return res;// 2Sum 是 base caseif (n 2) {// 双指针那一套操作int lo start, hi sz - 1;while (lo hi) {int sum nums[lo] nums[hi];int left nums[lo], right nums[hi];if (sum target) {while (lo hi nums[lo] left) lo;} else if (sum target) {while (lo hi nums[hi] right) hi--;} else {res.add(new ArrayList(Arrays.asList(left, right)));while (lo hi nums[lo] left) lo;while (lo hi nums[hi] right) hi--;}}} else {// n 2 时递归计算 (n-1)Sum 的结果for (int i start; i sz; i) {ListListIntegersub nSumTarget(nums, n - 1, i 1, target - nums[i]);for (ListInteger arr : sub) {// (n-1)Sum 加上 nums[i] 就是 nSumarr.add(nums[i]);res.add(arr);}while (i sz - 1 nums[i] nums[i 1]) i;}}return res;}
}
