网站项目需求分析,怎么查网站建设时间,电子商务网站建设 实验分析,广东中山市做网站文章目录 1.题目2.题目解答1.四数之和题目及题目解析算法学习代码提交 2.长度最小的子数组题目及题目解析滑动窗口的算法学习方法一#xff1a;单向双指针(暴力解法)方法二#xff1a;同向双指针(滑动窗口) 代码提交 1.题目
18. 四数之和 - 力扣#xff08;LeetCode#x… 文章目录 1.题目2.题目解答1.四数之和题目及题目解析算法学习代码提交 2.长度最小的子数组题目及题目解析滑动窗口的算法学习方法一单向双指针(暴力解法)方法二同向双指针(滑动窗口) 代码提交 1.题目
18. 四数之和 - 力扣LeetCode209. 长度最小的子数组 - 力扣LeetCode
2.题目解答
1.四数之和
题目及题目解析 算法学习 去重
外层固定的数要跳过相同的数内层固定的数也要跳过相同的数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:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint vv;vectorint v;sort(nums.begin(),nums.end());int i 0;while(inums.size()-1){int j i1;while(jnums.size()-1){int left j1;int rightnums.size()-1;long long int tmp (long long int)target-nums[i]-nums[j];while(leftright){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(leftrightnums[left]nums[left-1]){left;}while(leftrightnums[right]nums[right1]){right--;}}}j;while(jnums.size()-1nums[j]nums[j-1]){j;}}i;while(inums.size()-1nums[i]nums[i-1]){i;}}return vv;}
};2.长度最小的子数组
题目及题目解析 滑动窗口的算法学习
方法一单向双指针(暴力解法)
直接定义两个指针从前向后一次遍历,将所有的结果列举出来,直接进行求解
解法如下:
class Solution {
public:int minSubArrayLen(int target, vectorint 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指针没有必要每次都进行回退
可以让其一直保持在原有位置不变: 这也就是滑动窗口
当暴力解法两个指针都不回退且要对一部分的区间进行管理,就可以使用双指针解法
解法步骤如下:
初始化部分: 初始化窗口
循环部分 进窗口 判断是否出窗口(同时要记录值) 进窗口 判断是否出窗口(同时要记录值) 重复这两个步骤就可以得出我们想要的结果了 写成代码如下 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, vectorint nums) {int left 0,right 0;int sum 0;int len INT_MAX;for(;rightnums.size();right){sum nums[right];while(sumtarget){len min(len,right-left1);sum - nums[left];}}return lenINT_MAX?0:len;}
};
