关注并标星 3分钟秒懂大数据

每天1次，打卡阅读

获取AI大数据技术、面经、内推信息

第3天：双指针

1、Leetcode 283.移动零

1、题目介绍：

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

2、示例如下：

3、解题思路：

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：

左指针左边均为非零数；

右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

4、代码如下：

（1）JAVA版本

class Solution {    public void moveZeroes(int[] nums) {        int n = nums.length, left = 0, right = 0;        while (right < n) {            if (nums[right] != 0) {                swap(nums, left, right);                left++;            }            right++;        }    }
    public void swap(int[] nums, int left, int right) {        int temp = nums[left];        nums[left] = nums[right];        nums[right] = temp;    }}

（2）Python版本

class Solution:    def moveZeroes(self, nums: List[int]) -> None:        n = len(nums)        left = right = 0        while right < n:            if nums[right] != 0:                nums[left], nums[right] = nums[right], nums[left]                left += 1            right += 1

5、复杂度分析

2、Leetcode 167.两数之和 || 输入有序数组

1、题目介绍：

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

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

2、示例如下：

3、解题思路：

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

使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。

假设numbers[i]+numbers[j]=target 是唯一解，其中 0 <= i < j <= numbers.length-1是唯一解，初始时两个指针分别指向下标 0 和下标 numbers.length-1，左指针指向的下标小于或等于 i，右指针指向的下标大于或等于 j。

除非初始时左指针和右指针已经位于下标 i 和 j，否则一定是左指针先到达下标 i 的位置或者右指针先到达下标 j 的位置。

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

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

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

4、代码如下：

（1）JAVA版本

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

（2）Python3版本

class Solution:    def twoSum(self, numbers: List[int], target: int) -> List[int]:        low, high = 0, len(numbers) - 1        while low < high:            total = numbers[low] + numbers[high]            if total == target:                return [low + 1, high + 1]            elif total < target:                low += 1            else:                high -= 1
        return [-1, -1]

5、复杂度分析

以上就是14天算法入门-第3天-双指针讲解内容！觉得好的，点赞，在看，分享三连击，谢谢！！！

End

最近整理了一份计算机类的书籍，包含python、java、大数据、人工智能、算法等，种类特别齐全。

获取方式：关注公众号：3分钟秒懂大数据，回复：福利，就可以获得这份超级大礼！，小伙伴们快来领取吧。

点个在看你最好看

ITPub博客

14天算法入门-第3天-双指针

最新文章