一，移动零
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}; } };
复杂度分析
- 时间复杂度：O(n)，其中 nn 是数组的长度。两个指针移动的总次数最多为 n 次。
- 空间复杂度：O(1)。
以上部分来自力扣，由本人整理。
