当前位置：首页 > news >正文

算法刷题第三天：双指针--2

news 来源：原创 2024/5/17 4:42:19

一，移动零

思路及解法

复杂度分析

二，两数之和 II - 输入有序数组

1，二分查找

复杂度分析

2，双指针：

复杂度分析

一，移动零

283. 移动零 - 力扣（LeetCode）https://leetcode.cn/problems/move-zeroes/

思路及解法

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

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

注意到以下性质：

左指针左边均为非零数；

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

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

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

复杂度分析

时间复杂度：O(n)，其中 nn 为序列长度。每个位置至多被遍历两次。
空间复杂度：O(1)。只需要常数的空间存放若干变量。

二，两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

之前我们做过这样的一道题，要么直接暴力求解，要么用哈希表去找对应的解。

1，二分查找

在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int low = i + 1, high = numbers.size() - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return {i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return {-1, -1};
    }
};

复杂度分析

●时间复杂度: O(nlogn), 中n是数组的长度。需要遍历数组一次确定第一个数，时间复杂渡
是O(n),寻找第二个数使用二分查找，时间复杂度是O(logn),因此总时间复杂渡是O(n logn)
●空间复杂度: 0(1)。.

2，双指针：

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素
之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯-解。如果两个元素之和小于目
标值，则将左侧指针右移-位。如果两个元素之和大于目标值，则将右侧指针左移-位。移动指针之
后，鰒上述操作，直到找到答案。
使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉?答案是不会。假设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的左侧，因此不会
把可能的解过滤掉。于题目确保有唯一的答案，因此使用双指针一定可以找到答案。

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