双指针-＞算法实现
综述
移除元素：leetcode27
删除有序数组中的重复项：leetcode26
移动零：leetcode283
有序数组的平方：leetcode977
反转字符串：leetcode344
替换数字：非leetcode原题
反转字符串中的单词：leetcode151
三数之和：leetcode15
四数之和：leetcode18
引言
刷题总结
对于 移除元素，删除有序数组中的重复项，移动零 都是使用的 快慢指针 进行操作的，快慢指针很方便
很多数组填充类的问题，其做法都是先预先给数组扩容到填充后的大小，然后在从后向前进行操作。
比如：替换数字----非leetcode原题
对于 反转字符串中的单词，需要多做几遍，因为代码中的坑很多，不容易 bug free，可能需要多次 debug
移除元素
题目
题解
暴力：直接移动数组元素进行覆盖，时间复杂度是 O(n^2)
双指针：一个指针从前向后遍历，一个指针从后向前遍历，前向指针遍历到和 val 相等的元素，就和后向指针指向的元素交换，前提是后向指针指向的元素和 val 不相等
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int j = nums.size() - 1;
for (int i = 0; i <= j; i++) {
while (nums[j] == val) { //最后一个元素是 val，就 j--，使得交换的时候是 nums[j] 不是 val
j--;
if (j < 0) return j + 1; //防止减到0导致数组角标越界
}
if (i > j) break; //用于遍历到 i==j 时，如果 nums[j]==val，j就--，此时 j < i，如果再进行交换的话就出错了
if (nums[i] == val) {
std::swap(nums[i], nums[j]);
j--;
}
}
return j + 1;
}
};
时间复杂度是 O(n)
也可以使用一个快指针 和 慢指针，快指针遍历所有元素，只要快指针指到的元素不是 val，就覆盖慢指针指向的元素
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if(nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
};
时间复杂度：O(n)
删除有序数组中的重复项
题目
题解
上道题 nums 是无序的，要求返回的数组也是无序的
这道题 nums 是有序的，要求返回的数组也是有序的
代码和上道题只有一点区别
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];//区别，先++，再赋值
}
}
return slow + 1;//最后需要加1
}
};
移动零
题目
题解
只要 nums[fast] 不为0，就交换顺序
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
std::swap(nums[fast], nums[slow]);
slow++;
}
}
}
};
有序数组的平方
题目
题解
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
//双指针解决，设置左指针和右指针，谁的绝对值大谁的平方就放res的后面
vector<int> res(nums.size(), 0);
int left = 0;
int right = nums.size() - 1;
int index = nums.size() - 1;
while (left <= right) {
if (abs(nums[left]) < abs(nums[right])) {
res[index] = nums[right] * nums[right];
right--;
} else {
res[index] = nums[left] * nums[left];
left++;
}
index--;
}
return res;
}
};
反转字符串
题目
题解
简单题不多说
class Solution {
public:
void reverseString(vector<char>& s) {
int i = 0;
int j = s.size() - 1;
while (i < j) {
std::swap(s[i++], s[j--]);
}
}
};
替换数字
题目
题解
很多数组填充类的问题，其做法都是先预先给数组扩容到填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
- 不用申请新数组。
- 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
ACM 代码：
#include<iostream>
using namespace std;
class Solution {
public:
void ti_huan_number(string& s) {
//统计数字的个数
int count = 0;
for (char ele : s) {
if (ele >= '0' && ele <= '9') count++;
}
//扩充字符串
int beforeSize = s.size();
s.resize(beforeSize + count * 5);
//从后往前赋值
for (int i = beforeSize - 1, j = s.size() - 1; i >= 0; i--) {
if (s[i] >= '0' && s[i] <= '9') {
s[j--] = 'r';
s[j--] = 'e';
s[j--] = 'b';
s[j--] = 'm';
s[j--] = 'u';
s[j--] = 'n';
} else {
s[j--] = s[i];
}
}
}
};
int main() {
string s;
Solution solution;
while (cin >> s) {
solution.ti_huan_number(s);
cout << s <<endl;
}
return 0;
}
反转字符串中的单词
题目
题解
要求：不要使用辅助空间，空间复杂度要求为O(1)
如果使用辅助空间，那这道题就是简单题了，没意义
这道题得多练，里面坑很多，不容易一下子写出来，得debug较长时间
思路就是：先总体反转，再挨个反转单词，反转单词的过程中需要处理多个空格的情况
class Solution {
public:
string reverseWords(string s) {
//先删除尾随空格
int index = s.size() - 1;
while (s[index] == ' ') index--;
s.resize(index + 1);
//字符串整体颠倒顺序
reverse(s.begin(), s.end());
//按照空格为间隔，给每个单词再次颠倒顺序，需要注意多个空格删成一个空格
for (int i = 0, j = 0; j < s.size(); j++) {
if (s[j] == ' ' && s[j - 1] == ' ') continue; //处理多余空格
if (s[j] == ' ') {
reverse(s.begin() + i, s.begin() + j);
while (s[i] != ' ') i++;
i++;
}
if (j == s.size() - 1) reverse(s.begin() + i, s.end());
}
//删除尾随空格
index = s.size() - 1;
while (s[index] == ' ') index--;
s.resize(index + 1);
return s;
}
};
三数之和
题目
题解
如果是暴力，那么需要三层循环，时间复杂度是 O(n^3)
使用双指针的话，只需要两层循环即可，时间复杂度是 O(n^2)
思路：
- 首先将数组排序
- 外层循环遍历 i；内层循环遍历 left 和 right（left 是 i + 1，right 是 nums.size() - 1，只要 left < right，就循环
- 计算 nums[i] + nums[left] + nums[right]
如果 = 0，加入结果 res 中；如果 < 0，说明结果小了，让 nums[left] 变大（因为 nums[i] 不能变，nums[right] 只能变小），即 left++；如果 > 0，说明结果大了，让 nums[right] 变小，即 right- - - 注意：代码需要去重，即之前说过的数层去重，需要对 nums[i]，nums[left]，nums[right] 分别去重
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//先排序
sort(nums.begin(), nums.end());
//两层循环，判断 nums[i] + nums[left] + nums[right] 是否等于 0
vector<vector<int>> res;
for (int i = 0; i < nums.size() - 2; i++) {
if (i != 0 && nums[i] == nums[i - 1]) continue;//数层去重，去重nums[i]
int left = i + 1;
int right = nums.size() - 1;
//sum=0则放入res中；小于0说明三个数较小，让nums[left]变大；大于0...
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[right] == nums[right - 1]) right--; //数层去重，去重nums[right]
while (left < right && nums[left] == nums[left + 1]) left++; //数层去重，去重nums[left]
left++;
right--;
}
else if (sum < 0) left++;
else right--;
}
}
return res;
}
};
可以加上剪枝代码：
if (nums[i] > 0) {
return result;
}
排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
四数之和
题目
题解
思路和 三数之和 一样
三数之和 通过双指针 使 O(n^3) 变成了 O(n^2)
四数之和 通过双指针 使 O(n^4) 变成了 O(n^3)
四数之和 需要注意的是代码中间可能会有数值溢出的情况，需要将 int 类型转换成 long 类型
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end()); //排序
vector<vector<int>> res;
if (nums.size() < 4) return res;
for (int i = 0; i < nums.size() - 3; i++) { //第一个循环
if (i != 0 && nums[i] == nums[i - 1]) continue; //nums[i] 的数层去重
for (int j = i + 1; j < nums.size() - 2; j++) { //第二个循环
if (j != i + 1 && nums[j] == nums[j - 1]) continue; //nums[j] 的数层去重
int left = j + 1;
int right = nums.size() - 1;
while (left < right) { //第三个循环
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right]; //防止溢出
if (sum == target) {
res.push_back({nums[i], nums[j], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++; //nums[left] 的数层去重
while (left < right && nums[right] == nums[right - 1]) right--; //nums[right] 的数层去重
left++;
right--;
} else if (sum < target) left++;
else right--;
}
}
}
return res;
}
};
可以加上剪枝代码：
if (nums[i] + nums[j] > target && nums[j] >= 0) {
break;
}
因为只要 nums[i] + nums[j] > target，那么 nums[j] 后面的数都是正数的话，就一定 不符合条件了。