算法基础学习Day5(双指针、动态窗口)

1.题目

1. 18. 四数之和 - 力扣（LeetCode）
2. 209. 长度最小的子数组 - 力扣（LeetCode）

2.题目解答

1.四数之和

题目及题目解析

算法学习

去重：

1. 外层固定的数要跳过相同的数
2. 内层固定的数也要跳过相同的数
3. left和right也要跳过相同的数

这部分的代码如下：

int i = 0;
while (i < nums.size() - 1)
{int j = i + 1;while (j < nums.size() - 1){int left = j + 1;int right = nums.size() - 1;long long int tmp = (long long int)target - nums[i] - nums[j];while (left < right){if (nums[left] + nums[right] > tmp){right--;}else if (nums[left] + nums[right] < tmp){left++;}else{v.push_back(nums[i]);v.push_back(nums[left]);v.push_back(nums[right]);v.push_back(nums[j]);vv.push_back(v);v.clear();left++;right--;while (left < right && nums[left] == nums[left - 1]){left++;}while (left < right && nums[right] == nums[right + 1]){right--;}}}j++;while (j < nums.size() - 1 && nums[j] == nums[j - 1]){j++;}}i++;while (i < nums.size() - 1 && nums[i] == nums[i - 1]){i++;}
}

代码提交

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> vv;vector<int> v;sort(nums.begin(),nums.end());int i = 0;while(i<nums.size()-1){int j =i+1;while(j<nums.size()-1){int left =j+1;int right=nums.size()-1;long long int tmp = (long long int)target-nums[i]-nums[j];while(left<right){if(nums[left]+nums[right]>tmp){right--;}else if(nums[left]+nums[right]<tmp){left++;}else{v.push_back(nums[i]);v.push_back(nums[left]);v.push_back(nums[right]);v.push_back(nums[j]);vv.push_back(v);v.clear();left++;right--;while(left<right&&nums[left]==nums[left-1]){left++;}while(left<right&&nums[right]==nums[right+1]){right--;}}}j++;while(j<nums.size()-1&&nums[j]==nums[j-1]){j++;}}i++;while(i<nums.size()-1&&nums[i]==nums[i-1]){i++;}}return vv;}
};

2.长度最小的子数组

题目及题目解析

滑动窗口的算法学习

方法一：单向双指针(暴力解法)

直接定义两个指针从前向后一次遍历,将所有的结果列举出来,直接进行求解

解法如下:

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX;int n = nums.size();// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩// 枚举开始位置for (int start = 0; start < n; start++) {int sum = 0; // 记录从这个位置开始的连续数组的和// 寻找结束位置for (int end = start; end < n; end++) {sum += nums[end]; // 将当前位置加上if (sum >= target) // 当这段区间内的和满⾜条件时{// 更新结果，start 开头的最短区间已经找到ret = min(ret, end - start + 1);break;}}}// 返回最后结果return ret == INT_MAX ? 0 : ret;}
};

方法二：同向双指针(滑动窗口)

我们在使用暴力解法的时候发现

right指针没有必要每次都进行回退

可以让其一直保持在原有位置不变:

这也就是滑动窗口

当暴力解法两个指针都不回退且要对一部分的区间进行管理,就可以使用双指针解法

解法步骤如下:

初始化部分:

1. 初始化窗口

   

循环部分：

1. 进窗口

   

2. 判断是否出窗口(同时要记录值)

   

3. 进窗口

   

4. 判断是否出窗口(同时要记录值)

   

   重复这两个步骤就可以得出我们想要的结果了

   写成代码如下：

   int left = 0, right = 0;
   int sum = 0;
   int len = INT_MAX;
   for (;right < nums.size();right++)
   {sum += nums[right];while (sum >= target){len = min(len, right - left + 1);sum -= nums[left++];}
   }
   

代码提交

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left =0,right =0;int sum =0;int len = INT_MAX;for(;right<nums.size();right++){sum += nums[right];while(sum>=target){len = min(len,right-left+1);sum -= nums[left++];}}return len==INT_MAX?0:len;}
};