双指针

乘积小于K的子数组 原题链接：https://leetcode.cn/problems/ZVAVXX/ 1.静态滑动窗口 维护一个mul乘积 对乘积进行 * / 操作 当是当滑动窗口的长度len 非常大时， 乘积mul可能会超出数据范围 如果多个 0 ~ 1000 范围的num[i]相乘 可能超出 int 数据范围 这种方法非常容易超出int的数据范围 认定为失败的方法 123456789101112131415161718class Solution {public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { if (k == 0) return 0; int ans = 0; //遍历滑动窗口的长度 for (int len = 1; len <= nums.size(); ++len) { int mul = 1; int flag = 1; for (int i = 0; i < len; ++i) mul *= nums[i]; if (mul < k) ans++; for (int i = 1; i + len <= nums.size(); ++i) { mul /= nums[i - 1]; mul *= nums[i + len - 1]; if (mul < k) ans++; } } return ans; }}; 2.动态滑动窗口 从前往后处理所有的nums[i]，使用变量i、j代表窗口的左右端点（静态窗口弊端完美解决），使用变量mul记录当前窗口的乘积， 当 mul>=k 时，我们考虑将左端点i右移，同时消除左端点元素 nums[i] 对 mul 的贡献，直到mul>=k不再满足 这样就可以得到每个右端点 nums[i] 的最远左端 ...

排序数组中两个数字之和 原题链接：https://leetcode.cn/problems/kLl5u1/ 给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。 1.双指针1234567891011121314151617181920class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { vector<int> ans; int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { ans.push_back(low); ans.push_back(high); break; } else if (sum < target) { low++; } else if (sum > target) { high--; } } return ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(1)$ 2.二分查找12345678910111213141516171819202122class S ...

数组中和为0的三个数 原题链接：https://leetcode.cn/problems/1fGaJU/ 1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时， 123456789101112131415161718192021222324252627class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; //使用双指针解决剩余两个数字 for (int j = i + 1; j < nums.size(); ++j) { for (int k = j + 1; k < nums.size(); ++k) { if (nums[i] + nums[j] + nums[k] == 0) { //判定符合要求的答案是否重复 //ans.push_back({nums[i], nums[j], nums[k]}); if (ans.size() == 0) ans.push_back({nums[i], nums[j], nums[k]}); else { int flag = 1; for (in ...

双指针算法 1.算法模板1234for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++; /*具体问题逻辑*/} 常见双指针问题： 对于一个序列，用两个指针维护一段区间 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 2.双指针练习（1）AcWIng799.最长连续不重复子序列方法1：暴力法1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;const int MAX = 100010;int n;int a[MAX], mark[MAX];bool check(int low, int high) { for (int i = low + 1; i <= high; ++i) { for (int j = low; j < i; ++j) { if (a[i] == a[j]) return false; } } return true;}int main() { int res = 0; cin >> n; for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { if (check(j, i)) res = max(res, i - j + 1); } } cout << res << endl; return 0;} 方法2：双指针法仔细考虑暴力法就会发现，暴力法在解题时有很多地方是重复计算了： 比如 j = 0，i ...

合并两个有序数组 原题链接：https://leetcode.cn/problems/merge-sorted-array/ 给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。 注：最终合并后数组不应由函数返回，而是存储在数组 nums1 中。 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？ 1.双指针1234567891011121314151617181920212223242526272829//while循环写法class Solution {public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int k = m + n - 1; int i = m - 1, j = n - 1; while (i >= 0 && j >= 0) { if (nums1[i] >= nums2[j]) { nums1[k] = nums1[i]; i--; k--; } else { nums1[k] = nums2[j]; j--; k--; } } while (i >= 0) { nums1[k] = nums1[i]; i--; k--; } ...

移除指定元素 原题链接：https://leetcode.cn/problems/remove-element/ 1.巧妙的移动元素1234567891011121314class Solution {public: int removeElement(vector<int>& nums, int val) { int count = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == val) { count++; } else { nums[i - count] = nums[i]; } } return nums.size() - count; }}; 2.重复项删除类似12345678910111213class Solution {public: int removeElement(vector<int>& nums, int val) { int black = 0; for (int red = 0; red < nums.size(); ++red) { if (nums[red] != val) { nums[black] = nums[red]; black++; } } return black; }};

删除有序数组中的重复项 原题链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 不要使用额外的空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。 1.双指针1234567891011121314class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.size() == 0) return 0; int black = 0; for (int red = 1; red < nums.size(); ++red) { if (nums[red] != nums[black]) { black++; nums[black] = nums[red]; } } return black + 1; }};

两数之和 原题链接：https://leetcode.cn/problems/two-sum/ 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 1.暴力法1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; for (i = 0; i < nums.size(); ++i) { for (j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {i, j}; }}; 2.二分查找思想：sort排序 + 二分查找 使用for循环遍历数组中的每一个数字 在for循环内部，使用target值减去当前遍历的数字值获取配对值ret，使用二分查找该数字ret 如果找到该数字则直接输出其下标(初始若有序的情况下) 实际是无序的！难点在于如何联系被sort打乱下标后的vec与未打乱的nums，并从其中找出目标数字的下标？ 1234for (int j = 0; j < n; j++) { if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j); if(result.size() == 2) return result;} 12345678910111213141516171819202122 ...

OnlineJ两数之和 原题链接：http://oj.haizeix.com/problem/599 题目描述 给定一个从小到大的数组和一个目标数t，在其中找到两个数，使得两数之和与目标数相等，输出两个数在数组中的位置。 输入 第一行输入两个整数 n, t（1 ≤ n ≤ 1000000, 1 ≤ t ≤ 20000000） 接下来一行 n 个数，均小于10,000,000 输出 输出两个用空格隔开的数表示位置（从零开始计数），答案有唯一解 126 151 5 6 7 10 26 11 4 1.暴力法：1234567891011121314151617181920212223#include<iostream>#include<cstdio>using namespace std;int num[1000005];int n, target;int main() { scanf("%d%d", &n, &target); for (int i = 0; i < n; ++i) { scanf("%d", &num[i]); } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (num[i] + num[j] == target) { cout << i << " " << j << endl; return 0; } } } cout << "not fimd" << endl; return 0;} 注意：由于数据范围(1≤n≤1000000, 1≤t≤20000000)，暴力枚举的时间复杂度为O(n^2)一定会超时，空间复杂度为O(1) 2.二分法：=&# ...

Largest product in a series The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832. 73167176531330624919225119674426574742355349194934969835203127745063262395783180169848018694788518438586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557668966489504452445231617318564030987111217223831136222989342338030813533627661428280644448664523874930358907296290491560440772390713810515859307960866701724271218839987979087922749219016997208880937766572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397536978179778461740649551492908625693219784686224828397224137565705605749026140797296865241453510047482166370484403199890008895243450658541227588666881164271714799244429282308634656748139191231628245861786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408071984038509624554443629812309878799272442849091888458015616 ...