第三天——双指针

283.移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾。

同时保持非零元素的相对顺序。

必须在原数组上操作,不能拷贝额外的数组。

尽量减少操作次数。

public class Solution {
    public void MoveZeroes(int[] nums) {
        int n = nums.Length;
        int left = 0;
        int right = 0;

        while(right < n)
        {
            if(nums[right]!=0)
            {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
            right++;
        }
    }
}

我第一次做完才发现不能用额外数组

所以昨天那道很类似的题目的暴力思路就没用了

然后我就陷入了死循环完全没有双指针的思路

被迫去看了题解

简单来说是类似于快排的思想

只不过这里的值固定为0

现在有一个指针zero

还有一个指针change

两个都从0开始,change每次加1

假如change比0大(在这道题是必然的),就把这个数放到0的左边

也就是zero和change交换了位置,此时zero加1

第二次遇到同为0的数,zero不变

第三次遇到了非0的数,zero再次和change交换位置,zero加1

以此类推就可以实现双指针的思路了

可以参考:动画演示.移动零


167. 两数之和 II – 输入有序数组

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

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

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

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        int[] answer = new int[2];
        int n = numbers.Length;
        int left = 0;
        int right = n-1;

        while(left < right)
        {
            if(numbers[left] + numbers[right] == target)
            {
                answer[0] = left+1;
                answer[1] = right+1;
                break;
            }
            else if(numbers[left] + numbers[right] < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        
        return answer;
    }
}

这题算双指针里比较好理解的题目

加粗的地方如果都看到了就很好做了

我选择性忽略了一开始的非递减还卡了好一会

简单来说就是左右指针

每一次比较一下左指针+右指针的和是不是等于目标值

如果是的话直接输出成一维数组

如果比目标值来的小,因为是递增数列,那你只要向右移动left就能使和变大

同理比目标值来得大,你只要向左移动right就能使和变小

最后循环内就能得到答案

注意判断条件不能是left<=right

等号会重叠,就不符合题目最后一句话的不重复使用元素了

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注