数组双指针、滑动窗口练习

Question 1 0344. 反转字符串

经典的双指针练习题，定义左右指针分别指向 s 的第一个元素和最后一个元素，然后逐个交换位置，待到两个指针指向的元素相同时跳出即可。

 class Solution {
 public:
     void reverseString(vector& s) 
     {
         char temp = 0;
         int left = 0, right = s.size() - 1;
         while(left < right)
         {
             temp = s[left];
             s[left] = s[right];
             s[right] = temp;
             left++; right--;
         }
     }
 };

算法分析：

时间复杂度O(n)，其中n为s中元素数目的一半

空间复杂度O(1)

Question 2 0080. 删除有序数组中的重复项 II

这道题主要练习快慢指针，按照题目要求，只需要检查nums[right] 和 nums[left-2]是否相等即可。如果不等，则说明nums[right]所指向的元素应该被保留。

 class Solution {
 public:
     int removeDuplicates(vector& nums) 
     {
         int left = 2, right = 2;
         int n = nums.size();
         if(n <= 2)
         {
             return n;
         }
         for(int i = 2; i < n; i++)
         {
             if(nums[right] != nums[left-2])
             {
                 nums[left] = nums[right];
                 left++;
             }
             right++;
         }
         return left;
     }
 };

算法分析：

时间复杂度O(n)

空间复杂度O(1)

Question 3 0674. 最长连续递增序列

一道不定长度窗口的应用题。所求的数组长度即为窗口大小。

定义左右指针left 和 right，逐个比较nums[right]和nums[right-1]的大小即可。

 class Solution {
 public:
     int findLengthOfLCIS(vector& nums) 
     {
         int left = 0, right = 1;
         int n = nums.size();
         int ans = 0;
         if(n == 1)
         {
             return n;
         }
         while(right < n)
         {
             if(nums[right-1] < nums[right])
             {
                 right++;
             }
             else
             {
                 left = right;
                 right++;
             }
             ans = max(ans, (right-left));
         }
         return ans;
     }
 };

算法分析：

时间复杂度O(n)，需要遍历数组

空间复杂度O(1)