LeetCode-双指针问题
1 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路一：
找到一个元素删掉，把后面的往前推，复杂度太多 O(n^2)
思路二：
双指针法 ： 也是需要找个每个元素，然后把后一个元素上去，使用快慢指针
class Solution {
public:
int removeElement1(vector<int> &nums, int val) {
int slow = 0;
int fast;
for (fast = 0; fast < nums.size(); fast++) { //fast 遍历数组
if (nums[fast] != val) { //如果 这个值不等于 val
nums[slow++] = nums[fast]; // fast 覆盖 slow ，注意 如果没找到 slow 和 fast是相等的
// 如果找到了， 跳过if slow 没增加， fast+1 ，
}
}
return slow; //最后slow指针指向
}
};
2 移除元素 （升序）
给你一个 升序排列 的数组 nums ，请你\\ 原地\\\\ 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
依然采用双指针的方法，快指针遍历数组全部数据，慢指针停留在下一个不同元素的位置，为快指针覆盖表明位置
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 1) {
return* 1;
}
int slow = 0;
int fast;
for(fast = 0; fast < nums.size(); fast++) {
if (nums[slow] != nums[fast]) {
nums[++slow] = nums[fast]; //如果相等
}
}
return slow+1;
}
3.有序数组的平方
#给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1： 输入：nums = \[-4,-1,0,3,10\] 输出：\[0,1,9,16,100\] 解释：平方后，数组变为 \[16,1,0,9,100\]，排序后，数组变为 \[0,1,9,16,100\]
示例 2： 输入：nums = \[-7,-3,2,3,11\] 输出：\[4,9,9,49,121\]
思路： 很典型 的 双指针解法，两个指针分别指向首尾，平方后相比较，大的指针不动，小的移动
vector<int> sortedSquares(vector<int> &nums) {
if (nums.size() == 1) {
return {nums[0] * nums[0]};
}
int left = 0;
int right = nums.size() - 1;
vector<int> ret;
while (left <= right) {
if (nums[right] * nums[right] >= nums[left] * nums[left]) { //前后数值结果 比较，如果大取出来，移动指针
ret.push_back(nums[right] * nums[right]);
right--;
} else {
ret.push_back(nums[left] * nums[left]); //同理
left++;
}
}
return ret;
}
4.替换空格 4. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
思路：找出有多少个空格，然后扩容， 一个指针指向原来的末端，新的指针指向新的末端，将字符移动到最后端
string replaceSpace(string s) {
if(s.size()==0)
return "";
int count = 0;
for (auto ch : s) {
if (ch == ' ') count++;
}
int oldsize = s.size();
if (count == 0) return s;
s.resize(s.size() + count * 2);
int newsize = s.size();
for (int i = newsize - 1, j = oldsize - 1; j < i; i--, j--) {
if (s[j] != ' ')
swap(s[j], s[i]);
else if (s[j] == ' ') {
s[i--] = '0';
s[i--] = '2';
s[i] = '%';
}
}
return s;
}
5. 无重复字符的最长子串 5\. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路： 模拟一个滑动窗口，窗口右边界一直向右探索，知道探索的下一个字符，在窗口中已存在，若已存在则左边界收缩，现在问题是如何快速确定字符在窗口中已存在，可以利用 有hash特性的 unorderset ，快速查找字符是否存在
int lengthOfLongestSubstring(string s) {
unordered_set<char> win; //建立一个集合
int right = -1; //初始右边界
int ans = 0;
for (int i = 0; i < s.size(); i++) {
//第一次走到这不用剔除，接下来每一次走到这都说明遇到了相同的字符
if (i != 0) {
win.erase(s[i - 1]); //剔除窗口 的值
}
// 不断 扩展右边界 先试探下一个是否存在，所以right 初始化为-1
while (right + 1 < s.size() && !win.count(s[right + 1])) {
win.insert(s[right + 1]);
right++;
}
//通过下标推出长度
ans = max(ans, right - i + 1);
}
return ans;
}