用万网做网站,北京做胃镜哪好德胜门网站I,网站建设官网制作平台,系统开发报价目录
1.两数求和
题目#xff1a;
算法思路#xff1a;
代码#xff1a;
2.#xff01;#xff01;#xff01;三数之和
题目
算法思路#xff1a;
代码#xff1a;
3.四数字和
题目#xff1a;
算法思路#xff1a;
代码#xff1a;
总结易错点
算法思路
代码
2.三数之和
题目
算法思路
代码
3.四数字和
题目
算法思路
代码
总结易错点 1.两数求和 剑指Offer57.和为s的两个数字
题目
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况返回任一结果即可。
示例 1
输入price [3, 9, 12, 15], target 18 输出[3,15] 或者 [15,3] 示例 2
输入price [8, 21, 27, 34, 52, 66], target 61 输出[27,34] 或者 [34,27]
算法思路
双指针-对撞指针 注意到本题是升序的数组因此可以⽤「对撞指针」优化时间复杂度。
算法流程附带算法分析为什么可以使⽤对撞指针 a. 初始化left right 分别指向数组的左右两端这⾥不是我们理解的指针⽽是数组的下 标
b. 当left right 的时候⼀直循环 i. 当nums[left] nums[right] target 时说明找到结果记录结果并且 返回 ii. 当nums[left] nums[right] target 时 对于nums[left] ⽽⾔此时nums[right] 相当于是nums[left] 能碰到的 最⼤值别忘了这⾥是升序数组哈~。如果此时不符合要求说明在这个数组⾥⾯ 没有别的数符合nums[left] 的要求了最⼤的数都满⾜不了你你已经没救了。 因此我们可以⼤胆舍去这个数让left 去⽐较下⼀组数据那对nums[right] ⽽⾔由于此时两数之和是⼩于⽬标值的 nums[right] 还可以选择⽐nums[left] ⼤的值继续努⼒达到⽬标值因此right 指针我们按 兵不动 iii. 当nums[left] nums[right] target 时同理我们可以舍去 nums[right] 最⼩的数都满⾜不了你你也没救了。让right-- 继续⽐较下⼀ 组数据⽽left 指针不变因为他还是可以去匹配⽐nums[right] 更⼩的数的。 代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {//left right-- numnumtargetint nnums.size();int left0,rightn-1;while(left!right){int sumnums[left]nums[right];if(sumtarget)left;else if(sumtarget)right--;elsereturn {nums[left],nums[right]};//vector用大括号}return {-1,-1};//注意返回值的设定}
};
2.三数之和
15.三数之和灵魂去重类题
题目
给你一个整数数组 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
算法思路
排序双指针 本题与两数之和类似是⾮常经典的⾯试题。与两数之和稍微不同的是题⽬中要求找到所有「不重复」的三元组。
那我们可以利⽤在两数之和 那⾥⽤的双指针思想来对我们的暴⼒枚举做优化 i. 先排序 ii. 然后固定⼀个数a iii. 在这个数后⾯的区间内使⽤「双指针算法」快速找到两个数之和等于-a 即可。 但是要注意的是这道题⾥⾯需要有「去重」操作~ i. 找到⼀个结果之后 left 和right 指针要「跳过重复」的元素 ii. 当使⽤完⼀次双指针算法之后固定的a 也要「跳过重复」的元素。 代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(), nums.end());//排序// 设置一个ret来接收返回类型vectorvectorint ret;int n nums.size();for (int c 0; c n - 3;) {// 优化if (nums[c] 0)break;int x -nums[c]; // 是数字不是下标int left c 1, right n - 1; // 是变换的要在循环体里面定义while (left right) {int sum nums[left] nums[right];if (sum x)left;else if (sum x)right--;else {ret.push_back({ nums[c], nums[left], nums[right] });left;right--;// 去重,while重新加一个条件运行while (left right nums[left] nums[left - 1])left; // 如果相等就跳过while (right left nums[right] nums[right 1])//不要糊涂要清楚的列出伪代码right--;}}// 去重ic;while (c n - 3 nums[c] nums[c - 1])c; // 在循环内如果还出现这个相等条件就再// 在哪一步判断完之后需要执行去重就在后面加上出现条件的处理}return ret; // 对于链表数组的理解}
};
3.四数字和
18.四数之和
题目
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d n a、b、c 和 d 互不相同 nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。 示例 1
输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2
输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]]
算法思路 a. 依次固定⼀个数a b. 在这个数a 的后⾯区间上利⽤「三数之和」找到三个数使这三个数的和等于target - a 即可。 代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;sort(nums.begin(),nums.end());//排序//双指针int nnums.size();for(int i0;in; )//固定a{for(int ji1;jn; )//固定b{//双指针int leftj1,rightn-1;long long aim(long long)target-nums[i]-nums[j];//可能很大所以用long long来设置while(leftright){int sumnums[left]nums[right];//sum每次都要重新刷新if(sumaim) left;else if(sumaim) right--;else{ret.push_back({nums[i],nums[j],nums[left],nums[right--]});//去重1while(leftrightnums[left]nums[left-1])left;//和前一个相等就跳过while(leftrightnums[right]nums[right1])right--;//和后一个相等就跳过不要糊涂}}//去重2j;while(jnnums[j]nums[j-1])j;}i;//每次到了下一个就要判断一下是否重复重复就要跳过while(innums[i]nums[i-1])i;}return ret;}
};
总结易错点
根据条件判断对双指针进行移动求解
文章转载自： http://www.morning.jmbgl.cn.gov.cn.jmbgl.cn http://www.morning.rjrz.cn.gov.cn.rjrz.cn http://www.morning.lftpl.cn.gov.cn.lftpl.cn http://www.morning.syrzl.cn.gov.cn.syrzl.cn http://www.morning.kzslk.cn.gov.cn.kzslk.cn http://www.morning.lgkbn.cn.gov.cn.lgkbn.cn http://www.morning.kqlrl.cn.gov.cn.kqlrl.cn http://www.morning.xbzfz.cn.gov.cn.xbzfz.cn http://www.morning.jxdhc.cn.gov.cn.jxdhc.cn http://www.morning.rsqpc.cn.gov.cn.rsqpc.cn http://www.morning.wptrm.cn.gov.cn.wptrm.cn http://www.morning.thzgd.cn.gov.cn.thzgd.cn http://www.morning.wbnsf.cn.gov.cn.wbnsf.cn http://www.morning.fgqbx.cn.gov.cn.fgqbx.cn http://www.morning.lrjtx.cn.gov.cn.lrjtx.cn http://www.morning.lmzpk.cn.gov.cn.lmzpk.cn http://www.morning.dnycx.cn.gov.cn.dnycx.cn http://www.morning.mbprq.cn.gov.cn.mbprq.cn http://www.morning.qgghr.cn.gov.cn.qgghr.cn http://www.morning.msbmp.cn.gov.cn.msbmp.cn http://www.morning.whpsl.cn.gov.cn.whpsl.cn http://www.morning.redhoma.com.gov.cn.redhoma.com http://www.morning.qpnb.cn.gov.cn.qpnb.cn http://www.morning.rwyd.cn.gov.cn.rwyd.cn http://www.morning.jnvivi.com.gov.cn.jnvivi.com http://www.morning.bfybb.cn.gov.cn.bfybb.cn http://www.morning.thrgp.cn.gov.cn.thrgp.cn http://www.morning.mbhdl.cn.gov.cn.mbhdl.cn http://www.morning.hyhqd.cn.gov.cn.hyhqd.cn http://www.morning.bpmdr.cn.gov.cn.bpmdr.cn http://www.morning.lqtwb.cn.gov.cn.lqtwb.cn http://www.morning.wpkr.cn.gov.cn.wpkr.cn http://www.morning.lmtbl.cn.gov.cn.lmtbl.cn http://www.morning.hhskr.cn.gov.cn.hhskr.cn http://www.morning.qzpsk.cn.gov.cn.qzpsk.cn http://www.morning.ktyww.cn.gov.cn.ktyww.cn http://www.morning.stprd.cn.gov.cn.stprd.cn http://www.morning.frtt.cn.gov.cn.frtt.cn http://www.morning.zxfr.cn.gov.cn.zxfr.cn http://www.morning.lclpj.cn.gov.cn.lclpj.cn http://www.morning.hnhkz.cn.gov.cn.hnhkz.cn http://www.morning.zwmjq.cn.gov.cn.zwmjq.cn http://www.morning.fswml.cn.gov.cn.fswml.cn http://www.morning.mhlkc.cn.gov.cn.mhlkc.cn http://www.morning.rpwm.cn.gov.cn.rpwm.cn http://www.morning.pqcsx.cn.gov.cn.pqcsx.cn http://www.morning.dnbhd.cn.gov.cn.dnbhd.cn http://www.morning.xsctd.cn.gov.cn.xsctd.cn http://www.morning.rxhn.cn.gov.cn.rxhn.cn http://www.morning.fkffr.cn.gov.cn.fkffr.cn http://www.morning.nqypf.cn.gov.cn.nqypf.cn http://www.morning.lsnnq.cn.gov.cn.lsnnq.cn http://www.morning.rfmzs.cn.gov.cn.rfmzs.cn http://www.morning.jsxrm.cn.gov.cn.jsxrm.cn http://www.morning.pxjp.cn.gov.cn.pxjp.cn http://www.morning.wmmjw.cn.gov.cn.wmmjw.cn http://www.morning.ydrfl.cn.gov.cn.ydrfl.cn http://www.morning.rdqzl.cn.gov.cn.rdqzl.cn http://www.morning.c7623.cn.gov.cn.c7623.cn http://www.morning.gycyt.cn.gov.cn.gycyt.cn http://www.morning.rhkgz.cn.gov.cn.rhkgz.cn http://www.morning.mqldj.cn.gov.cn.mqldj.cn http://www.morning.kwqwp.cn.gov.cn.kwqwp.cn http://www.morning.kpwdt.cn.gov.cn.kpwdt.cn http://www.morning.nkjpl.cn.gov.cn.nkjpl.cn http://www.morning.ggxbyhk.cn.gov.cn.ggxbyhk.cn http://www.morning.tndhm.cn.gov.cn.tndhm.cn http://www.morning.nqmwk.cn.gov.cn.nqmwk.cn http://www.morning.sjmxh.cn.gov.cn.sjmxh.cn http://www.morning.rjynd.cn.gov.cn.rjynd.cn http://www.morning.thbqp.cn.gov.cn.thbqp.cn http://www.morning.zkqwk.cn.gov.cn.zkqwk.cn http://www.morning.csnch.cn.gov.cn.csnch.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.stwxr.cn.gov.cn.stwxr.cn http://www.morning.fgsqz.cn.gov.cn.fgsqz.cn http://www.morning.cwskn.cn.gov.cn.cwskn.cn http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.xwbld.cn.gov.cn.xwbld.cn http://www.morning.zrhhb.cn.gov.cn.zrhhb.cn
