LeetCode-双指针问题

Last updated on 8 months ago

1 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路一：

​ 找到一个元素删掉，把后面的往前推，复杂度太多 O(n^2)

思路二：

​ 双指针法 ： 也是需要找个每个元素，然后把后一个元素上去，使用快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

依然采用双指针的方法，快指针遍历数组全部数据，慢指针停留在下一个不同元素的位置，为快指针覆盖表明位置

1
2
3
4
5
6
7
8
9
10
11
12
13
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]

思路：很典型 的 双指针解法，两个指针分别指向首尾，平方后相比较，大的指针不动，小的移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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.替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

思路：找出有多少个空格，然后扩容， 一个指针指向原来的末端，新的指针指向新的末端，将字符移动到最后端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

思路： 模拟一个滑动窗口，窗口右边界一直向右探索，知道探索的下一个字符，在窗口中已存在，若已存在则左边界收缩，现在问题是如何快速确定字符在窗口中已存在，可以利用 有hash特性的 unorderset ，快速查找字符是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}