力扣每日一练之双指针 2Day9

🍕前面的话🥞

大家好！本篇文章将介绍 20 天算法刷题计划的题，本文将以两道题作为背景，介绍经典的双指针，展示语言为 java（博主学习语言为 java)。今天呢，是博主开始刷力扣的第九天，如果有想要开始准备自己的算法面试的同学，可以跟着我的脚步一起，共同进步。大家都是并肩作战的伙伴，一起努力奋力前行，路漫漫其修远兮，吾将上下而求索，相信我们一定都可以拿到自己期望的 offer，冲冲冲！

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn 首发！

😘系列专栏：java 学习

💻首发时间：🎞2022 年 5 月 12 日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🔏参考在线编程网站：🎧力扣

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

🏓导航小助手📻

[TOC]

图片

🤗Leetcode283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:
输入: nums = [0]输出: [0]

😪解题思路

我们创建两个指针 i 和 j，第一次遍历的时候指针 j 用来记录当前有多少非 0 元素。即遍历的时候每遇到一个非 0 元素就将其往数组左边挪，第一次遍历完后，j 指针的下标就指向了最后一个非 0 元素下标。第二次遍历的时候，起始位置就从 j 开始到结束，将剩下的这段区域内的元素全部置为 0。

😚源代码

class Solution {    public void moveZeroes(int[] nums) {      if(nums==null||nums.length==0){          return;      }      int[] tmp=new int[nums.length];      int j=0;      for(int i=0;i<nums.length;i++){          if(nums[i]!=0){              tmp[j]=nums[i];              j++;          }      }      for(int i=0;i<nums.length;i++){          nums[i]=tmp[i];      }    }}

🥰Leetcode167.两数之和二之输入有效数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：
输入：numbers = [2,7,11,15], target = 9输出：[1,2]解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6输出：[1,3]解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3：
输入：numbers = [-1,0], target = -1输出：[1,2]解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

😴解题思路

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。假设 \textit{numbers}[i]+\textit{numbers}[j]=\textit{target}numbers[i]+numbers[j]=target 是唯一解，其中 0 \leq i<j \leq \textit{numbers}.\textit{length}-10≤i<j≤numbers.length−1。初始时两个指针分别指向下标 00 和下标 \textit{numbers}.\textit{length}-1numbers.length−1，左指针指向的下标小于或等于 ii，右指针指向的下标大于或等于 jj。除非初始时左指针和右指针已经位于下标 ii 和 jj，否则一定是左指针先到达下标 ii 的位置或者右指针先到达下标 jj 的位置。

如果左指针先到达下标 ii 的位置，此时右指针还在下标 jj 的右侧，\textit{sum}>\textit{target}sum>target，因此一定是右指针左移，左指针不可能移到 ii 的右侧。

如果右指针先到达下标 jj 的位置，此时左指针还在下标 ii 的左侧，\textit{sum}<\textit{target}sum<target，因此一定是左指针右移，右指针不可能移到 jj 的左侧。

由此可见，在整个移动过程中，左指针不可能移到 ii 的右侧，右指针不可能移到 jj 的左侧，因此不会把可能的解过滤掉。由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。

🤩源代码

class Solution {    public int[] twoSum(int[] numbers, int target) {        int left=0,right=numbers.length-1;        while(left<right){            int currentSum=numbers[left]+numbers[right];            if(currentSum==target){                return new int[]{left+1,right+1};            }else if(currentSum<target){                left++;            }else{                right--;            }        }        return new int[]{-1,-1};    }}

🌌总结

通过这两道题，我们学习了双指针，复习了数组和循环的知识，那么呢，期待一下下一篇文章吧，和我一起进步，每天努力多一些，迈出更大的一步

觉得文章写的不错的亲亲，点赞评论关注走一波，爱你们哦🛴