002_双指针法

1.移除元素

目标：移除数组中的某一个元素

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

1.1暴力解法

建立两个for循环，当查找到某个元素以后，将此元素后面的元素全部往前移动

时间复杂度：

1.2双指针法

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

快指针用来遍历全部的数组元素，慢指针用来更新数组元素，当快指针的元素不是要删除的元素的时候，赋值给慢指针

时间复杂度：

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
class Solution1 {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; size--; }}return size;}
};class Solution2 {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};int main()
{vector<int> array1 = { 1 ,2,4,4,5,5,5,6,7,8 };Solution1 solution1;int size1 = solution1.removeElement(array1, 5);for (int i = 0; i <size1; i++){cout << array1[i] << " ";}cout<<endl;vector<int> array2 = { 1 ,2,4,4,5,5,5,6,7,8 };Solution2 solution2;int size2 = solution2.removeElement(array2, 5);for (int i = 0; i <size2; i++){cout << array2[i] << " ";}return 0;
}

2.有序数组的平方

要求：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 ： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

2.1暴力解法

每个数平方以后，排个序

class Solution {
public:vector<int> sortedSquares(vector<int>& A) {for (int i = 0; i < A.size(); i++) {A[i] *= A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
};

2.2双指针法

由于数组是有序的，平方以后，最大的肯定出现在两端，因此令k为最大索引，依次往前排列

双指针：i从左往右索引，j从右往左索引，将大的值赋值给nums[k]，然后k--

class Solution {
public:vector<int> sortedSquares(vector<int>& A) {int k = A.size() - 1;vector<int> result(A.size(), 0);for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素if (A[i] * A[i] < A[j] * A[j])  {result[k--] = A[j] * A[j];j--;}else {result[k--] = A[i] * A[i];i++;}}return result;}
};

3.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
 

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组

3.1暴力解法

建立两个for循环，然后不断的寻找符合条件的子序列

3.2滑动窗口

只使用一个for循环，循环的索引是滑动窗口的终止位置。

指针1：滑动窗口的终止位置，依次往右移动

指针2：滑动窗口的起始位置，同样也是一直往右移动

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX;int sum = 0; // 滑动窗口数值之和int i = 0; // 滑动窗口起始位置int subLength = 0; // 滑动窗口的长度for (int j = 0; j < nums.size(); j++) {sum += nums[j];// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件while (sum >= s) {subLength = (j - i + 1); // 取子序列的长度result = result < subLength ? result : subLength;sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};

        滑动窗口本质上也是一种双指针法，是在充分理解题目的情况下，暴力算法的一种简化
        这道题之所以可以使用滑动窗口，很重要的一个原因是，在移动终止位置的时候，初始位置是不可逆的，初始位置只可能往后移动，而不用每次都从第零个元素开始
       所有双指针法，都是充分利用题目的一个隐藏的特征，来对暴力算法的一种简化