当前位置：首页 > article >正文

算法系列之双指针(待完善题目)

article 2025/3/3 20:37:44

1.简介

双指针是指在遍历数据结构（如数组、链表等）时，使用两个指针变量来辅助解决问题的方法。这两个指针可以同时移动，也可以一个指针固定而另一个指针移动，通过对指针的操作和相互配合，能够更高效地处理数据，解决各种问题。

2.对向指针

也叫左右指针，两个指针分别从数据结构的两端开始，相向移动。常用于数组的排序、回文串的判断等问题。例如在快速排序算法中，就可以利用对向双指针来划分数据。

2.1分类

教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以数组形式返回。

注意是数组

class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        int i=0;
        int j=actions.size()-1;
        while(i<j)
        {
            while(i<j&&(actions[i]&1)==1)i++;
            while(i<j&&(actions[j]&1)==0)j--;
            swap(actions[i],actions[j]);
        }
        return actions;
        
    }
};

2.2回文串

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int>res;
        while(head)
        {
            res.push_back(head->val);
            head=head->next;
        }
        for(int i=0,j=res.size()-1;
                    i<j;i++,j--)
                    {
                        if(res[i]!=res[j])
                        return false;
                    }
                    return true;
        

    }
};

链表不好用双指针建议转化为数组

3.同向指针（滑动窗口）

两个指针从同一端开始，向同一方向移动。例如在有序数组中寻找满足特定条件的元素对时，通常可以使用同向双指针。一个指针用于遍历数组，另一个指针在当前指针的基础上进行特定条件的搜索和判断。

3.1 文件组合

待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

输入：target = 18
输出：[[3,4,5,6],[5,6,7]]
解释：在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        vector<vector<int>>res;
        int i=0;
        int j=1;
        int s=i+j;
        while(i<j)
        {
            if(s==target)
        
            {
                vector<int>tmp;
                for(int k=i;k<=j;k++)
                {
                    tmp.push_back(k);
                }
                res.push_back(tmp);
            }
            if(s<target)
            {
                j++;
                s+=j;
            }
            if(s>=target)
            {
                s-=i;
                i++;
            }
            
        }
        return res; 
    }
};

满足条件==左边界才能移动

3.2 重复子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合，记录每个字符是否出现过
        unordered_set<char> tmp;
        int n = s.size();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int right = -1, res = 0;
        // 枚举左指针的位置，初始值隐性地表示为 -1
        for (int left = 0; left < n; ++left) {
            if (left!= 0) {
                // 左指针向右移动一格，移除一个字符
                tmp.erase(s[left - 1]);
            }
            while (right + 1 < n && !tmp.count(s[right + 1])) {
                // 不断地移动右指针
                tmp.insert(s[right+ 1]);
                right++;
            }
            // 第 left到 right个字符是一个极长的无重复字符子串
            res = max(res, right - left + 1);
        }
        return res;
    }
};

4 快慢指针

两个指针移动速度不同，快指针每次移动的步长大于慢指针。在链表相关问题中经常使用，比如判断链表是否有环、寻找链表的中间节点等。快指针一次移动两步，慢指针一次移动一步，如果链表有环，快指针最终会追上慢指针。

4.1回文链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr)
        {
            return false;
        }
        ListNode*slow=head;
        ListNode*fast=head->next;
        while(slow!=fast)
        {
            if(fast==nullptr||fast->next==nullptr)
            {
                return false;
            }
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
        
      
    }
};

4.2

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast=head;
        ListNode *dum=new ListNode(0,head);
        ListNode *slow=dum;
        for(int i=0 ;i<n;i++)
        {
            fast=fast->next;
        }
        while(fast)
        {
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dum->next;}
      
};