1.移动零1.1题目解析1.2算法原理这道题可以归为数组划分数组分块这类题中特点是分成两个不同的区域利用双指针算法利用数组下标来充当指针定义两个指针curdest两个指针的作用cur 从左往右扫描数组遍历数组dest 已处理的区间内非零元素的最后一个位置三个区间[0,dest]非0[dest1,cur-1]0[cur,n-1]待处理为什么第二个区间是cur-1回到cur的定义上cur是从左往右扫描数组遍历这个数组的如何做到cur从前往后遍历的过程中遇到0元素cur遇到非0元素交换元素swap(dest1,cur);dest;cur;1.3编写代码class Solution { public void moveZeroes(int[] nums) { for(int cur0,dest-1;curnums.length;cur){ if(nums[cur]!0){ dest; int tmpnums[cur]; nums[cur]nums[dest]; nums[dest]tmp; } } } }2.复写零2.1题目解析2.2算法原理解法:双指针算法先根据异地操作,然后优化成双指针下的就地操作先找到最后一个复写的数;从后向前完成复写操作.怎么找复写的数?双指针算法先判断cur位置的值决定dest向后移动一步或两步判断一下dest是否已经到结束为止cur;注意:cur和dest的执行顺序,dest先移动,再判断有没有出界,如果没有cur;如果dest越界,直接跳出循环cur也就不用移动。处理边界情况? n-1 -0 ;cur--;dest-2;2.3代码实现class Solution { public void duplicateZeros(int[] arr) { int cur0; int dest-1; int narr.length; //1.找最后一个复写的数 while(curn){ if(arr[cur]!0){ dest1; }else{ dest2; } if(destn-1) break; cur; } //2.处理边界情况 if(destn){ arr[n-1]0; cur--; dest-2; } //3.从后向前完成复写操作 while(cur0) { if(arr[cur]!0) arr[dest--]arr[cur--]; else{ arr[dest--]0; arr[dest--]0; cur--; } } } }3.快乐数3.1题目解析3.2算法原理解法快慢双指针定义快慢指针慢指针每次向后移动一步快指针每次向后移动两步判断相遇时候的值即可注意slow和fast不能一开始都定义为n,不然循环都进不去3.3代码实现class Solution { public int bitSum (int n){ //返回n 这个数每一位的平方和 int sum0; while(n!0){ int tn%10; //个位数 sumt*t; n/10; } return sum; } public boolean isHappy(int n) { int slown; int fastbitSum(n); while(slow!fast){ slowbitSum(slow); fastbitSum(bitSum(fast)); } return slow1; } }4.盛水最多的容器4.1题目描述4.2算法原理解法一暴力枚举 On^2超时解法二利用单调性使用双指针来解决问题 O(n)左右指针从两端出发 面积较小高度*指针距离每次只移动较小的数过程中记录最大面积为什么呢因为面积受限于较小的数如果移动较高的数由于宽度变小了 但水的高度上限不变面积不可能变大只有移动较小的数才有机会遇到面积最大4.3代码实现class Solution { public int maxArea(int[] height) { int left0; int rightheight.length-1; int ret0; //记录结果 while(leftright){ int vMath.min(height[left],height[right])*(right-left); retMath.max(ret,v); if(height[left]height[right]){ left; }else{ right--; } } return ret; } }5.有效三角形的个数5.1题目解析5.2算法原理补充数学知识给我们三个数判断是否能够构成三角形如果三角形三条边为a,b,cabc满足abc构成三角形优化先对这个数组排序解法一:暴力枚举 O(n^3)//伪代码for(int i0;in;i){for(int ji1;jn;j){for(kj1;kn;k){check(i,j,k);解法二:利用单调性,使用双指针算法来解决问题 O(n^2)先固定最大的数在最大的数的左区间内,使用双指针算法,快速统计出符合要求的三元组的个数5.3代码实现class Solution { public int triangleNumber(int[] nums) { //1.排序 Arrays.sort(nums); int ret0;// 结果 int nnums.length; //2.固定最大的数 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的两个数字6.1题目解析6.2算法原理解法一:暴力枚举的策略 O(n^2)//伪代码for(int i0;in;i){for(int ji1;jn;j){check(nums[i]nums[j]t);解法二:利用单调性,使用双指针算法解决问题sum t : right--sum t : leftsum t :返回结果6.3代码实现class Solution { public int[] twoSum(int[] price, int target) { int left0; int rightprice.length-1; while(leftright){ int sumprice[left]price[right]; if(sumtarget){ right--; }else if(sumtarget){ left; }else{ return new int[] {price[left],price[right]}; } } return new int[]{0}; } }7.三数之和7.1题目解析7.2算法原理解法一 : 排序暴力枚举利用set去重 O(n^3)解法二 : 排序双指针排序;固定一个数a; a0;在该数后面的区间内,利用双指针算法快速找到两个的和等于 -a即可.处理细节问题:去重 找到一种结果之后,left 和right 指针要跳过重复元素 , 当使用完一次双指针短算法之后, i 也需要跳过重复元素注意 : 避免越界不漏 找到一种结果之后,不要停,缩小区间,继续寻找7.3代码实现class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger retnew ArrayList();//结果 //1.排序 Arrays.sort(nums); //2.利用双指针解决问题 int nnums.length; int i0; //固定数a while(in){ if(nums[i]0) break; int lefti1; int rightn-1; int target-nums[i]; while(leftright){ int sumnums[left]nums[right]; if(sumtarget){ right--; }else if(sumtarget){ left; }else{ //找到一个符合条件的 ret.add(new ArrayListInteger(Arrays.asList(nums[i],nums[left],nums[right]))); left;right--; //去重 left right while(leftright nums[left]nums[left-1]){ left; } while(leftright nums[right]nums[right1]){ right--; } } } i; //去重 i while(in nums[i]nums[i-1]){ i; } } return ret; } }8.四数之和8.1题目解析8.2算法原理解法一:排序暴力枚举利用set去重解法二: 排序双指针依次固定一个数a;在 a 后面的区间内,利用三数之和找到这三个数,使得这三个数的和等于target - a即可三数之和:依次固定一个数 b ;在 b 后面的区间内,利用双指针找到两个数,使这两个数的和等于target - a - b 即可.处理细节问题:不重不漏8.3代码实现class Solution { public ListListInteger fourSum(int[] nums, int target) { ListListInteger retnew ArrayList(); //1.排序 Arrays.sort(nums); //利用双指针解决问题 int nnums.length; for(int i0;in;){ //固定数a for(int ji1;jn;){ //固定数b //三数之和 int leftj1; int rightn-1; long aim(long)target-nums[i]-nums[j]; 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(left right nums[left]nums[left-1]){ left; } while(left right nums[right]nums[right1]){ right--; } } } j; //去重 j while(jn nums[j]nums[j-1]) j; } i; //去重 i while(in nums[i]nums[i-1]) i; } return ret; } }