做百度移动网站优化排,深圳做企业网站的公司推荐,排名优化公司电话,关于家乡的网页制作教程本文主要讲解三数之和的要点与细节#xff0c;主要讲解利用双指针的方法解决#xff0c;按照步骤一步步思考方便理解 给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[…本文主要讲解三数之和的要点与细节主要讲解利用双指针的方法解决按照步骤一步步思考方便理解 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组 c与java代码如下末尾
具体要点 1. 本题核心要点在于三元组里面的数的顺序是不重要的结果不能包含重复的三元组 这就要求我们要对结果进行去重的操作也是本题最需要考虑清楚的 2. 这道题我们可以采用双指针滑动窗口或者 哈希表的方法来处理但是相比于哈希表双指针考虑去重要更简单一点我们先重点讲解双指针的解法 3. 一直说去重去重到底是什么呢
去重的核心操作是判断上一个或者下一个值是否等于当前值若等于就跳过再去判断下一个 4. 所以我们第一步就要对数组进行排序目的是让相同的值都挨在一起方便去重 5. 然后我们for循环遍历数组获取a的值即nums[i]
然后我们需要考虑一下a去重的问题如果 i 和 i-1 位置的值相等那么就跳过这里有小细节最后讲 if (i 0 nums[i] nums[i - 1]) continue; 6. 接着在anums[i]条件下定义两个指针 left i 1 和 right nums.size() - 1其值分别代表b和c 记录 sumnums[i] nums[left] nums[right] 然后就开始滑动通过判断sum和0的大小 若sum0则right-- 若sum0则left 若sum0则把i、left、right加入结果 7. 当我们 “sum0则把i、left、right加入结果”之后我们需要向中间移动left和right但是移动后位置会出现和上个位置重复值的情况此时我们就要对 b 和 c 去重了
//对b去重,此时判断的是下一个位置因为要确定移动到哪
while (left right nums[right] nums[right - 1]) right--;
//对c去重此时判断的是下一个位置因为要确定移动到哪
while (left right nums[left] nums[left 1]) left;
//直到没有重复的我们就正常移动
left;
right--;
最后返回result即可 8. 细节问题 abc去重操作一样吗好像还不太一样 a比较的是 nums[i] 与 nums[i - 1]。是和移动的上一个进行比较 b和c比较的是 nums[right] nums[right - 1] 与 nums[left] nums[left 1]。是和移动的下一个位置进行比较虽然right是-left是但是他们是往中间移动 为什么a的i不能和i1比较呢 因为i1的位置放的是left呀b a不需要和b进行去重呀abc三者重复是可以的 理解不了举个例子nums{-1-1-2} a是第一个-1如果i和i1比较下一个也是-1就跳过咯a直接指向第二个-1left和right也取不到第一个-1就错了 c代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {//定义一个vector保存结果vectorvectorint result;//对数组排序sort(nums.begin(), nums.end());for (int i 0; i nums.size(); i) {if (nums[i] 0)return result;//对a去重此时判断的是上一个位置如果判断的是下一位就大错特错因为下一位放的是leftleft和i相等是不影响结果的if (i 0 nums[i] nums[i - 1]) continue;//定义两个指针int left i 1;int right nums.size() - 1;//执行滑动操作while (left right) {int sumnums[i] nums[left] nums[right];if (sum 0) {right--; }else if (sum 0) {left;}else {result.push_back(vectorint{nums[i], nums[left], nums[right]});//对b去重,此时判断的是下一个位置因为要确定移动到哪while (left right nums[right] nums[right - 1]) right--;//对c去重此时判断的是下一个位置因为要确定移动到哪while (left right nums[left] nums[left 1]) left;left;right--;}}}return result;}
};
java代码
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();//先排序Arrays.sort(nums);for (int i 0; i nums.length; i) {if (nums[i] 0) return result;//去重aif (i 0 nums[i] nums[i - 1]) continue;//定义双指针int left i 1, right nums.length - 1;//双指针滑动while (left right) {int sum nums[i] nums[left] nums[right];if(sum0){right--;}else if (sum 0) {left;}else {//等于0添加进resulresult.add(Arrays.asList(nums[i], nums[left], nums[right]));//添加完成后移动b和c准备对下一个位置循环在此之前要先去重操作不然移动了还会有重复的while (left right nums[left] nums[left 1]) left;while (left right nums[right] nums[right - 1]) right--;//去重完成移动b和cright--;left;}}}return result;}
}
