注自2023下半年开始力扣里“剑指 Offer”前缀统一改成了“LCR”目录283. 移动零 - 力扣LeetCode1089. 复写零 - 力扣LeetCode202. 快乐数 - 力扣LeetCode11. 盛最多水的容器 - 力扣LeetCode611. 有效三角形的个数 - 力扣LeetCode1. 两数之和 - 力扣LeetCodeLCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCodeLCR 007. 三数之和 - 力扣LeetCode18. 四数之和 - 力扣LeetCode283. 移动零 - 力扣LeetCode算法逻辑①定义两个变量des、cur起始位置分别为-1、0②规定cur在遇到非零元素时交换“des1”位置的元素descur在遇到零元素时不做处理③这样一来就达到了以下图示的样子代码演示class Solution1 { public void moveZeroes(int[] nums) { int destination -1; for (int cur 0; cur nums.length; cur) { if(nums[cur] ! 0){ swap(nums,destination1,cur); destination; } } } public void swap(int[]array,int x,int y){ int tmp array[x]; array[x] array[y]; array[y] tmp; } }1089. 复写零 - 力扣LeetCode算法逻辑① 初始阶段演示如果cur指向非零元素cur和des各向前走一步如果cur指向零元素cur向前走一步des向前走两步因为要复写一个零这样做是为了找到从后向前复写的 cur 的位置因为经过推演从前向后会导致 des 比 cur 快漏写数据⬇️复写完成后的数组应该为如下des大多数情况下会超出数组范围只有少数特例恰好停在末尾比如当前这个。因此用des n - 1作为终止条件可以同时覆盖到达末尾和超出范围两种情况。②解决完寻找复写位置的问题就需要解决一个特殊情景如右图即des刚好处于数组末尾后一个位置n说明数组末尾位置n-1需要被复写为 0直接手动设置并将指针前移两位避免后续循环中访问arr[des]时des n发生数组越界③ 上述两步处理完成后从des指向的位置开始按既定规则从后向前复写元素直到数组全部填满代码演示public void duplicateZeros(int[] arr) { int n arr.length; int des -1; int cur 0; for (; cur n; cur) { if(arr[cur] ! 0){ des; }else { des2; } if(des n - 1){ break; } } if(des n -1){ arr[des-1] 0; des-2; cur--; } for (;cur 0; cur--) { if(arr[cur] ! 0){ arr[des] arr[cur]; des--; }else { arr[des] 0; arr[des - 1] 0; des-2; } } }202. 快乐数 - 力扣LeetCode算法逻辑①根据题目描述一个数最终只有两种结果1、变成 1快乐数2、进入循环非快乐数②因此循环的终止条件就是检测到环快慢指针相遇③使用快慢指针时fast的初始值应该比slow快一步即先计算一次平方和否则两者起点相同循环无法进入。④能走出while只能说明有循环不能说明是快乐数因此最终判断的条件应该是快慢指针撞车的地方是不是终点 1代码演示class Solution3{ public boolean isHappy(int n) { int slow n; int fast sum(n); while (slow ! fast){ slow sum(slow); fast sum(sum(fast)); } return slow 1; } public int sum(int n){ int sum 0; int t; while (n ! 0){ t n % 10; sum t * t; n n / 10; } return sum; } }这个是采用存放元素的形式没有使用双指针的写法class Solution3 { public boolean isHappy(int n) { LinkedListInteger x new LinkedList(); //不断拿到新的n值并判断 while (n ! 1 !x.contains(n)){ x.add(n); n getSquare(n); } return n 1; } //计算数字各位的平方和 public int getSquare(int n){ int sum 0; while (n 0){ sum (n % 10) * (n % 10); n / 10; } return sum; } }11. 盛最多水的容器 - 力扣LeetCode算法逻辑① 双指针基于暴力枚举主要注意其背后的思想它利用了单调性原理定义左右双指针从两端向中间移动。每次比较两端高度移动较矮的那一侧指针因为容器的宽度一直在减小只有放弃当前较短的边才可能遇到更高的边来弥补宽度的损失。如此重复直到指针相遇即可得到最大面积代码演示暴力枚举public int maxArea(int[] height) { int n height.length; int max Integer.MIN_VALUE; int area; int min; for (int left 0; left n - 1; left) { for (int right n - 1; right left; right--) { min Math.min(height[left],height[right]); area (right - left) * min; if(area max){ max area; } } } return max; }双指针public int maxArea(int[] height) { int left 0; int right height.length-1; int max 0; while (left ! right){ int area Math.min(height[left],height[right]) * (right-left); max Math.max(area,max); if(height[left] height[right]){ right--; }else { left; } } return max; }611. 有效三角形的个数 - 力扣LeetCode算法逻辑① 双指针解法基于对暴力枚举的优化只要排序后只要两小边之和 ≤ 最大边就不能构成三角形单调性原理② 所以先排序然后从右往左枚举最大边。每一轮用双指针若nums[left] nums[right] max则累加(right - left)并将右指针左移尝试更小的右边否则将左指针右移尝试更大的左边。最后累加所有结果即可③外层循环确定最大值内层计算本轮有效三角形个数时间复杂度为O(n^2)代码演示暴力枚举public int triangleNumber(int[] nums) { int sum 0; for (int c nums.length - 1; c 0; c--) { for (int a 0; a c; a) { for (int b a 1; b c; b) { //在数组无序的状态下三个条件同时满足才能判断构成三角形 if(nums[a] nums[b] nums[c] nums[b] nums[c] nums[a] nums[a] nums[c] nums[b]) { sum; } } } } return sum; }双指针public int triangleNumber(int[] nums) { int sum 0; //1、排序 Arrays.sort(nums); //2、第一层确定最大值下标 for (int max nums.length - 1; max 1; max--) { int left 0; int right max - 1; //3、第二层统计符合要求的三元组个数 while (right left){ if(nums[left] nums[right] nums[max]){ //动态变化 sum right - left; right--; }else { left; } } } return sum; }1. 两数之和 - 力扣LeetCodeLCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode算法逻辑① 两数之和LeetCode 1本质是无序数组的暴力枚举。而第二题LCR 179 / 剑指 Offer 57虽然也可以用暴力枚举但由于数组有序可以利用单调性提前结束循环比无序数组的写法更优。这里直接采用最优解法---双指针② 利用单调性总和大于target则right--总和小于target则left代码演示暴力枚举//暴力枚举无序数组 public int[] twoSum2(int[] nums, int target) { for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if(nums[i] nums[j] target){ return new int[]{i,j}; } } } //照顾编译器 return new int[]{}; }双指针public int[] subarraySum(int[] nums, int target) { //1、排序 Arrays.sort(nums); int left 0; int right nums.length - 1; while (left right){ if( nums[left] nums[right] target ){ return new int[] { nums[left], nums[right] }; }else if( nums[left] nums[right] target ){ right--; }else { left; } } //照顾编译器 return new int[]{}; }LCR 007. 三数之和 - 力扣LeetCode算法逻辑①三数之和又相当于双指针解决两数之和的延申。数组排序固定一个数nums[i]作为target在当前target之后用双指针寻找满足条件的两数之和②需要着重注意的两点不漏、去重不漏当找到一组符合条件的组合时左右指针继续移动左指针右移、右指针左移继续寻找当前target下的其他解而不是直接break去重1、左边去重、右边去重、target去重 2、要考虑到去重时的边界情况代码演示暴力枚举set去重两个deBuff//写法一暴力枚举 public ListListInteger threeSum(int[] nums) { //1、排序 Arrays.sort(nums); //2、利用Set去重 SetListInteger result new HashSet(); //3、三重循环枚举所有三元组 for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { for (int k j 1; k nums.length; k) { if(nums[i] nums[j] nums[k] 0){ //4、将满足条件的三元组转换成List放入Set result.add(Arrays.asList(nums[i],nums[j],nums[k])); } } } } return new ArrayList(result); }双指针手动去重//写法二双指针 public ListListInteger threeSum2(int[] nums) { //1、排序 Arrays.sort(nums); ListListInteger list new LinkedList(); //2、双指针 int left; int right; int i 0; int n nums.length - 2; while (i n){ //小优化 if(nums[i] 0){ break; } left i 1; right nums.length - 1; while (left right){ if(nums[left] nums[right] nums[i] 0){ list.add(Arrays.asList(nums[i],nums[left],nums[right])); //找到了也不能停下 //此处可结合单调性理解 left; right--; //分别对左右去重 //每次去重时都检查下是否越界了 while (left right nums[left] nums[left - 1]){ left; } while (left right nums[right] nums[right 1]){ right--; } }else if(nums[left] nums[right] nums[i] 0){ right--; }else { left; } } i; //对i去重 //为啥不写成ileft? 因为left不固定一直在移动 while (i n nums[i] nums[i - 1]){ i; } } return list; }18. 四数之和 - 力扣LeetCode算法逻辑①比三数之和多固定一个数因此外层多一层循环②每多固定一个数就多一次去重操作③最内层依然使用双指针解决两数之和代码演示public ListListInteger fourSum(int[] nums, int target) { //1、排序 Arrays.sort(nums); ListListInteger list new LinkedList(); //2、双指针 int left; int right; int x 0; int i 0; int n nums.length - 2; while (x n - 1){ i x 1; while (i n){ left i 1; right nums.length - 1; while (left right){ long sum (long) nums[x] nums[left] nums[right] nums[i]; if(sum target){ list.add(Arrays.asList(nums[x],nums[i],nums[left],nums[right])); left; right--; while (left right nums[left] nums[left - 1]){ left; } while (left right nums[right] nums[right 1]){ right--; } }else if(sum target){ right--; }else { left; } } i; //对i去重 while (i n nums[i] nums[i - 1]){ i; } } x; //对x去重 //注意这里的边界 while (x n - 1 nums[x] nums[x - 1]){ x; } } return list; }本专题完