北京棋森建设有限公司网站,外贸网站建站注意事项及价格,太原seo网站管理,网站怎么百度收录18. 四数之和
18. 四数之和 - 力扣#xff08;LeetCode#xff09; 给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] #xff08;若两个四元组元素一一对应LeetCode 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d n a、b、c 和 d 互不相同 nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2
输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]]
解法一排序 暴力枚举 理由set去重
超时
解法二排序 双指针
[-2, -1, 0, 0, 1, 2] target [ ] target - a a b [ ] target - a - b left right1. 先依次固定一个a;2. 在a后面的区间内利用“三数之和”找到三个数使这三个数的和等于target - a即可
三数之和的大体思路1. 依次固定一个b;2. 在b后面的区间内利用“双指针”找到两个数使这两个数的和等于target - a - b即可
处理细节问题1. 不重 去重a,b,left,right
2. 不漏
时间复杂度O(N^3)
代码C
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;// 排序sort(nums.begin(), nums.end());// 利用双指针解决问题int n nums.size();for(int i0; in; ) //固定a{// 利用三数之和for(int ji1; jn; ) //固定b{// 双指针int left j1, right n-1;long long aim (long long)target - nums[i] - nums[j];while(leftright){int sum nums[left] nums[right];if(sum aim) left;else if(sum aim) right--;else{ret.push_back({nums[i], nums[j], nums[left], nums[right--]});// 去重1while(left right nums[left] nums[left - 1]) left; //当left右移完之后和左边这个数相比如果相同说明重复元素需要跳过while(left right nums[right] nums[right 1]) right--;}}// 去重2j;while(j n nums[j] nums[j - 1]) j;}// 去重3i;while(i n nums[i] nums[i - 1]) i;}return ret;}
};
209. 长度最小的子数组
209. 长度最小的子数组 - 力扣LeetCode 解法一暴力枚举出所有子数组的和
时间复杂度O(N^3) R [2, 3, 1, 2, 4, 3] L 先定义一个sum计算左区间的和 比如sum 2 3 ... 这样可以省去再遍历一遍数组 R [2, 3, 1, 2, 4, 3] L sum 5 R [2, 3, 1, 2, 4, 3] L sum 6 len 2 - 3
... R [2, 3, 1, 2, 4, 3] L sum 12 len 5
这个len是一直增长的所以肯定不是最短的结果
接下来让L向左移动一位然后继续让R从左开始移动 那这个时候从3开始的区间可以在上一个结果中找到
解法二利用单调性使用“同向双指针”来优化也就是 滑动窗口
当使用暴力解法时。两个指针都可以做到不回退都是向一个方向移动时就可以使用滑动窗口
1. 初始化left 0, right 0
2. 进窗口
3. 判断是否是结果然后更新结果长度再出窗口判断len
2和3一直循环
以下是图解 4. 为什么不往后枚举呢因为已经知道接下来的情况再枚举也是白枚举因为是正整数数组 利用单调性规避了很多没有必要的枚举行为
5. 时间复杂度 进窗口要一个循环判断也是一个循环等于是两层循环套在一起 但是总的操作次数只是2n次 所以最终的时间复杂度是一个O(N)
代码C
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size();int sum 0, len INT_MAX; //如果定义0那最终的求min结果就是0所以定义一个大的变量不干扰最终结果for(int left 0, right 0; right n; right){// 进入窗口sum nums[right];//判断要不要缩小窗口while(sum target){len min(len, right - left 1); // 更新结果sum - nums[left]; // 出窗口}// 一直更新到窗口不符合要求位置然后right}return len INT_MAX ? 0 : len; // 如果没有最终结果就返回0不然就返回len}
};
3. 无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣LeetCode 子串和字数组都是连续的一段
解法一暴力枚举 哈希表(判断字符是否重复出现)
可以借助哈希表来判断是否有重复字符 遍历的时候把字符保存到哈希表里当遍历到重复元素时停止这个操作 R [d, e, a, b, c, a, b, c, a] L R [d, e, a, b, c, a, b, c, a] L
当a重复时停止这个操作然后移动L R [d, e, a, b, c, a, b, c, a] L
时间复杂度O(N^2)
解法二利用规律使用“滑动窗口”来解决问题 R [d, e, a, b, c, a, b, c, a] L R [[d, e, a, b, c], a, b, c, a] L
当a重复时停止这个操作然后移动L R [[d, e, a, b, c], a, b, c, a] L
当发现区间里面有重复字符时可以让L先跳过这个重复字符 R也不用回到L的位置让R继续移动即可 此时就可以使用滑动窗口解决问题
1. 先定义L 0和R 0
2. 进窗口 - 让字符进入哈希表
3. 判断 根据判断结果判定是否出窗口窗口内出现重复字符时才出窗口
判断和出窗口是一个循环一直到没有重复字符为止
出窗口就是从哈希表中删除该字符
然后更新结果更新结果的过程要根据题目决定在哪 本题中在整个判断之后更新结果
为什么要用滑动窗口因为两个指针都不会回退
时间复杂度ON 空间复杂度O1 因为哈希表只有128位所以可以忽略不计
代码C
class Solution {
public:int lengthOfLongestSubstring(string s) {// 下标表示字符让里面的数来表示是否重复出现出现一次为1两次为2...int hash[128] {0}; // 使用数组表示哈希表int left 0, right 0, n s.size();int ret 0;while(right n){hash[s[right]]; // 字符对应的下标进入窗口while(hash[s[right]] 1) // 判断{hash[s[left]]--; // 先把哈希表里面的对应的值--表示它从哈希表删除然后完成出窗口的操作}ret max(ret, right - left 1); // 更新结果区间的长度是right - left 1right; // 让下一个元素进入窗口}return ret;}
};
1004. 最大连续1的个数 III
1004. 最大连续1的个数 III - 力扣LeetCode 最多k个0说明可以翻转0,1,2...一直到k个为止 比如下方这个例子中k最多可以翻转100个0但其实不需要翻转100次 [1,1,0,0,1,1,0], k 100
[1,1,1,0,0,0,1,1,1,1,0], K 2 [ ]最长为6
可以等价处理在数组中满足0的个数不超过k次即可只要这个区域的0不超过k那么这个区域是一定可以翻转成功的 把原始问题转换成 找出最长的子数组0的个数不超过k个
解法一暴力枚举 zero计数器(int类型变量统计0出现多少次) R [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K 2 L zero 0 R [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K 2 L zero 1 R [[1, 1, 1, 0, 0], 0, 1, 1, 1, 1, 0], K 2 固定第一个位置的最优解 L zero 2
然后R继续从数组最开始的位置开始移动
解法二滑动窗口
所以可以让R越过这段区域不用重新遍历可以移动L R [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K 2 L
当在暴力枚举中L和R都只往一个方向移动时可以使用滑动窗口
1. left 0, right 0
2. 进窗口 - 如果是1无视如果是0计数器1 当R向后移动时就相当于进窗口了 当进入窗口时无视当碰到0时计数器加一
3. 判断 - 当zero大于k出窗口 出窗口 让L一直右移直到窗口合法为止
当判断结束之后更新结果当R移动到最后位置就会得到最终结果
时间复杂度O(N) 空间复杂度O(1)
代码C
class Solution {
public:int longestOnes(vectorint nums, int k) {int ret 0;for(int left 0, right 0, zero 0; right nums.size(); right){if(nums[right] 0) zero; // 进窗口while(zero k) // 判断窗口是否合法{if(nums[left] 0) zero--; // 出窗口left向后移动} // 左闭右闭的区间ret max(ret, right - left 1); // 更新结果}return ret;}
};
