双指针的问题解法以及常见的leetcode例题。

目录

介绍：

问题1：双指针 剑指offer57  和为S的两个数字。

问题2：剑指Offer 21. 调整数组顺序使奇数位于偶数前面

问题3：连续奇数子串（笔试遇到的真题）

问题4：滑动窗口的最大值

---

介绍：

双指针的问题通常需要理解问题的核心，然后选择合适的双指针策略来解决问题。以下是一种通用的解决方法：

1. 首先，对数组进行排序，这样相同的元素会在一起，并且可以更好地控制数组的遍历。
2. 定义两个指针，一个快指针和一个慢指针。通常，快指针是慢指针的两倍速度。
3. 从数组的两侧开始遍历，比较两个指针指向的元素之和与目标值的大小。
4. 根据和的大小调整指针的位置，例如，如果和等于目标值，则将两个指针都向后移动一位。如果和小于目标值，则慢指针向后移动一位，快指针向前移动两位。如果和大于目标值，则慢指针向前移动一位，快指针向后移动两位。
5. 当快指针和慢指针相遇时，就找到了解。

这种解决方案适用于很多问题，但是具体实现需要根据问题的具体要求进行调整。

问题1：双指针 剑指offer57  和为S的两个数字。

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/?envType=study-plan-v2&envId=coding-interviews

tag:easy.

// 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：因为已经排序完成了，定义了两个指针.从两侧进行即可。

输入：nums = [2,7,11,15], target = 9

输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40

输出：[10,30] 或者 [30,10]

class Solution10
{
public:vector<int> twoSum(vector<int> &nums, int target){vector<int> ans;int left = 0, right = nums.size() - 1;while (left <= right){if (nums[left] + nums[right] == target){ans.push_back(nums[left]);ans.push_back(nums[right]);break;}else if (nums[left] + nums[right] > target){right--;}else{left++;}}return ans;}
};

问题2：剑指Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/?envType=study-plan-v2&envId=coding-interviews。

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一

class Solution11 {
public:vector<int> exchange(vector<int>& nums) {int left=0;int right=0;while(right<nums.size()){if(nums[right]%2!=0){swap(nums[left++],nums[right++]);}else{right++;}}return nums;}};

问题3：连续奇数子串（笔试遇到的真题）

若有一组最小值大于0，数目大于1的连续的奇数的和等于指定正整5数

字，那么此连续的奇数序列称为此正整数数字的一个奇序列。如数字12，总共能找出一个奇序列 (5，7)，数字16 能找出两个奇序列 (1，3，5,7)和(7，9)

数字17 找不出，那么12的奇序列数为1，16的奇序列数为2，17的奇序列数为0。

输入 17

输入 0

输入 16

输出 2

输入 12

输出 1

函数用于计算奇序列数  从1 开始 加到 n/2，计算累计和超过n进入while 循环. 如果等于就是+2， 否则就停止。

1 3 5 7 9 11

 3 5 7 9

5 7 9 。。。小于n就可以了。 

int main()
{int n;cin >> n;int start = 0;int count = 0;int sum = 0;int i = 0;for (start = 1; start < n / 2; start += 2){i = start;sum = 0;while (sum < n){sum += i;i += 2;}if (sum == n){count++;}}cout << count << endl;system("pause");return 0;
}

问题4：滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值

 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k)   {int n=nums.size();priority_queue<pair<int,int>> q;for(int i=0;i<k;i++){q.emplace(nums[i],i);}vector<int> ans={q.top().first};for(int i=k;i<n;i++){q.emplace(nums[i],i);//离开了滑动窗口里面了，永久移除了while(q.top().second<=i-k){q.pop();}ans.push_back(q.top().first);}return ans;}};

      ======================待补充===========================