1.移动零题目链接283. 移动零 - 力扣LeetCode题目解析该题要求将数组中为0的元素全部转移到数组的末尾同时不能改变非零元素的相对位置。解题思路我们可以用变量dest和cur将该数组分为三个区域。如下图接着我们可以将数组中为0的元素放在[0,dest]的区域将数组中非0的元素放在[dest1,cur-1]的区域而[cur,n-1]是待处理的区域。等数组中全部处理完之后就如下图所示。实现思路我们用cur来遍历数组如果cur遇到数据为0的元素则让cur。如果cur遇到非0的元素因为要将非0数据放在[dest1,cur-1]区域所以我们先将dest然后交换nums[dest]和nums[cur]的值。代码实现public void moveZeroes(int[] nums) { int dest-1; for(int cur0;curnums.length;cur){ if(nums[cur]!0){ dest; int tmpnums[cur]; nums[cur]nums[dest]; nums[dest]tmp; } } }2.复写零题目链接1089. 复写零 - 力扣LeetCode解题思路我们可以用一个cur指针和一个dest指针用cur指针来遍历数组并且用来确定复写的数用dest来实现复写的操作。首先我们想到从前往后复写但此时我们会发现当cur遇到0的时候我们用dest来实现复写的时候由于0要复写2次此时会将cur后面没实现复写的一个数覆盖掉这样就会漏掉一个数没法实现复写。所以我们要从后往前实现复写。步骤1.首先我们要找到最后一个复写的数 。我们也可以用双指针实现找到最后一个复写的数。用cur来遍历数组我们先让dest指向-1的位置当cur遇到数据为非0的数我们让dest向后走两步如果cur遇到数据为0的数我们让dest向后走一步直到dest走到数组的末尾或者大于末尾的位置。步骤2.其次我们从后向前实现复写的操作我们也是通过cur来遍历数组当cur遇到非0的数据让dest向前走一步如果cur遇到数据为0的数我们让dest向前走两步。但是在此之前我们要处理一个边界情况也就是当我们返现当数组中最后一个要复写的数是0且该数是数组中倒数第二个数的时候dest会越界。如下图最后我们实现从后向前的复写就行了。如下图public void duplicateZeros(int[] arr) { int cur0; int dest-1; int narr.length; //寻找最后一个复写的数 while(curn){ if(arr[cur]!0){ dest1; }else{ dest2; } if(destn-1){ break; } cur; } //处理边界情况 if(destn){ arr[dest-1]0; dest-2; cur--; } //实现从后向前复写 while(cur0){ if(arr[cur]!0){ arr[dest--]arr[cur]; }else{ arr[dest--]0; arr[dest--]0; } cur--; } }3.快乐数题目链接202. 快乐数 - 力扣LeetCode解题思路通过题目例子我们来手动演示以下判断该数是否为快乐数的的过程。通过手动演示我们发现在判断数据是否为快乐数的过程中我们发现数据的变化会成为一个环。也就是说在这个过程中数据迟早会有一次演变成环中的数。我们将上图抽象成如下图的情况当我们抽象成右边图的时候这就更我们在学习链表中求链表是否存在环的情况很相似。不过在这里我们不是判断链表中是否有环而是判断环中的数据是否为1。前面我们在解决判断链表中是否有环的时候用了快慢指针这道题我们也可以用快慢指针。我们每次让slow一次变化一次让fast一次变换两次。这里的变换是指在判断是否为快乐数的过程中数据的变换。以一开始的19为例slow变化一次就是82fast变化两次就是68。public int bitSum(int n){ int sum0; while(n!0){ int tmpn%10; sumtmp*tmp; nn/10; } return sum; } public boolean isHappy(int n) { int slown; //由于要进入循环我们一开始就要将fast放在slow后面 int fastbitSum(n); while(slow!fast){ slowbitSum(slow);//让slow往后走一步 fastbitSum(bitSum(fast));//fast往后走两步 } return slow1; }拓展这时候有人就会疑惑又没有可能一个数据在变换的过程中会一直变化下去不会成环呢答案就是数据在进行变化的过程中变化的数据一定会成环。证明这就涉及到一个鸽巢原理。鸽巢原理当有n1只格子和n个鸽巢的时候必定会有一个鸽巢的鸽子数量大于等于1也就是总会有至少两只鸽子共享一个窝。此时我们将题目的数据观察题目的数据范围如下图n的最大值为2147483647相同位数的最大值为9999999999推出数据变化的范围在[1,810]之间。所以我们可以达到数据在变化的过程中变化的数肯定在[1,810]之间。我们就算他变化无数次变化的数据还是在[1,810]之间所以可以得出变化的过程中数据一定会成环。4.盛水最多的容器题目链接11. 盛最多水的容器 - 力扣LeetCode解法思路对撞指针和单调性我们可以设一个指针left指向数组中的第一个元素指针right指向最后一个元素(right-left)的值就是宽Math(height[left],height[right])就是高接着根据高和宽求面积。由于题目要求是求最大的面积所以我们要改变left和right的指向的位置分别求处不同情况下的面积然后再这些面积中求一个最大值即可。我们以何种方式来改变left合right指向的位置呢我们一次只变一个要么让left要么right--我们知道面积宽*高而宽right-left而再left的过程中或者是right--的过程中宽度的值一定是减小的。所以我们让height[left]和height[right]中数值较小的值移动。为什么呢这就涉及到单调性。如下图解释我们让指向值较小的指针位置变换实质上是放弃这个较小数的枚举因为以这个数枚举的面积都是在单调减小的所以我们就让数值较小的指针移动。代码实现public int maxArea(int[] height) { int nheight.length; int left0; int rightn-1; int v0; while(leftright){ int tmpMath.min(height[left],height[right])*(right-left); vMath.max(v,tmp); if(height[left]height[right]){ left; }else{ right--; } } return v; }5.有效三角型个数题目链接611. 有效三角形的个数 - 力扣LeetCode解法思路双指针和单调性首先我们先普及一个判断三角型的知识点如果我们知道abc,那么我们只需判断abc成立就可以判断这三条边可以组成三角形。所以我们可以先给数组进行排序这是一步优化。接着我们就可以先固定一个最大数因为数组排过序是一个有序数组那么这个最大数的左边的数是肯定都比这个最大数小的。接着建立如下图的指针位置这时我们就来判断a,b,c能否组成三角形。如果此时a,b,c三条边能组成三角形那么此时以9为b边10为c边能够成三角形的个数就为right-left 个因为数组是一个有序的数组那么(left,right)区间里的数都是大于a的数那么此时就不用通过枚举b边为9的情况下能组成三角形的情况了。如下图遇到这种情况我们就让right - -就行了此时会遇到第二种情况此时nums[left]nums[right]nums[i],此时我们直接让left就行了。因为此时(left,right)区间都是小于nums[right]的数了所以我们此时就不必要以nums[left]为基准去枚举了此时我们直接将此时的2去掉及让left就行了。知道left和right指针相遇我们在更换最大边循环以上步骤。代码实现public int triangleNumber(int[] nums) { Arrays.sort(nums); //固定最大数 int ret0,nnums.length; for(int in-1;i2;i--){//固定最大边 int left0; int righti-1; while(leftright){ if(nums[left]nums[right]nums[i]){ retright-left; right--; }else{ left; } } } return ret; }6.和为s的两个数字题目链接LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode解法一暴力枚举法但是当数组中的数据太多时会超时。public int[] twoSum(int[] nums, int target) { int nnums.length; for(int i0;in;i){ for(int ji1;jn;j){ if(nums[i]nums[j]target){ return new int[]{nums[i],nums[j]}; } } } return new int[]{-1,-1}; }解法二双指针此时我们注意题目中的数组是一个有序数组所以此题我们可以利用数组的单调性和双指针进行优化。我们分别设置一个left指针和一个right指针先让left指向数组中的第一个数据让right指向数组的最后一个数据然后我们根据left和right指向值的和与target进行比较不同的情况让不同指针移动。如下图此时left和right指针在移动的过程中会遇到三种情况。我们先假设left和right指向的值的和为sum。第一种情况 sumtarget如果是sumtarget的情况此时因为数组是一个有序数组而left指向的值是数组中最小的值right指向的值是数组中最大的值最小值与最大值的和还是小于target的值那么此时left指向的值与[left1,right]区间的任何一个值相加都是小于target的所以我们就可以大胆得放弃left指向值得枚举即让left。第二种情况sumtarget如果是sumtarget的情况最小值与最大值的和都大于target了那么此时right指向的值与[left,right-1]区间的任何一个值相加都是大于target的所以此时我们可以大胆的放弃此时right指向值得枚举情况。第三种情况sumtarget这种情况直接返回left和right指向的值就行了。代码实现public int[] twoSum(int[] price, int target) { int nprice.length; int left0; int rightn-1; while(leftright){ if(price[left]price[right]target){ right--; }else if(price[left]price[right]target){ left; }else{ return new int[]{price[left],price[right]}; } } return new int[]{-1,-1}; }7.三数之和题目链接15. 三数之和 - 力扣LeetCode题目解析求数组中三个数的和为0并且要求三个数是数组下表不同的数并且结果集中的一个子集不能重复出现子集中的数据顺序也不做要求。解法一双指针法求三个数的和为0我们也可以用求两数之和的方法来解决该问题。无非我们先固定一个数去求另外两个数之和为固定数的相反数就行了。 求两数之和和第6题的一摸一样。不过该题我们要去处理几个细节问题。细节一去重当left和right指针遇到相同元素之后我们要跳过该元素。当i也遇到重复元素时i也要跳过相同的元素。细节二不漏当ileft和right遇到一个符合情况的三元组时我们继续让leftright--。为了方便去重我们可以先对数组排序。代码实现public ListListInteger threeSum(int[] nums) { int nnums.length; Arrays.sort(nums);//对数组排序 ListListInteger retnew ArrayList(); for(int i0;in;){ if(nums[i]0) break;//小优化当nums[i]0时就可以跳出循环 int target-nums[i]; int lefti1; int rightn-1; while(leftright){ int sumnums[left]nums[right]; if(sumtarget) right--; else if(sumtarget) left; else{ ret.add(Arrays.asList(nums[i],nums[left],nums[right])); left; right--; while(leftrightnums[left]nums[left-1]) left;//去重 while(leftrightnums[right1]nums[right]) right--;//去重 } } i; while(innums[i]nums[i-1]) i;//去重 } return ret; }小细节我遇到的错误解法二暴力枚举法我们可以 通过排序枚举set去重不过会超时。class Solution { public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger ret new ArrayList(); SetListInteger set new HashSet(); int len nums.length; for(int i 0; i len; i) { for(int j i1; j len; j) { for(int k j1; k len; k) { if(nums[i] nums[j] nums[k] 0) { set.add(Arrays.asList(nums[i],nums[j],nums[k])); } } } } ret.addAll(set); return ret; } }8.四数之和题目链接18. 四数之和 - 力扣LeetCode解题思路思路和三数之和的思路差不多不过有个例子时会超出int的最大值所以需要我们用long来存储。代码实现public ListListInteger fourSum(int[] nums, int target) { Arrays.sort(nums); int nnums.length; ListListInteger retnew ArrayList(); for(int i0;in;){ for(int ji1;jn;){ long aim(long)target-nums[i]-nums[j]; int leftj1; int rightn-1; while(leftright){ int sumnums[left]nums[right]; if(sumaim) right--; else if(sumaim) left; else{ ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right])); left; right--; while(leftrightnums[left-1]nums[left]) left; while(leftrightnums[right1]nums[right]) right--; } } j; while(jnnums[j-1]nums[j]) j; } i; while(innums[i-1]nums[i]) i; } return ret; }