双指针的问题解法以及常见的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(rightsize()){
             
            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       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

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

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