目录
一，移动零
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)。
以上部分来自力扣，由本人整理。