双指针 - 简书

一、双指针总结

1.1题目

快慢指针（主要解决链表中的问题）

141.环形链表
142.环形链表 II
876.链表的中间结点
剑指 Offer 22. 链表中倒数第k个节点

左右指针

704.二分查找
167.两数之和 II - 输入有序数组
15.三数之和（去重）
11.盛最多水的容器

滑动窗口（两个指针从一个起点出发）

209.长度最小的子数组
76.最小覆盖子串（hard）
3.无重复字符的最长子串
剑指 Offer 57 - II. 和为s的连续正数序列

1.2滑动窗口的思路

1.不断扩张窗口，寻找一个可行解；
2.不断收缩窗口，优化这个可行解，直到不满足条件；
3.重复1、2，即寻找下一个可行解，然后再优化。

（适用于求最小的问题，求最大的问题要改一下，不过代码结构差不多）

int left = 0, right = 0;

while (right < s.size()) {
    window.add(s[right]);

    while (valid) {
        window.remove(s[left]);
        left++;
    }
    right++;
}

稍微⿇烦的地⽅就是这个 valid 条件。

二、题目

141.环形链表

思路1：哈希表

bool hasCycle(ListNode *head) {
    if (!head) return false;
    set<ListNode*> st;
    
    while (head) {
        if (st.count(head)) {
            return true;
        }else{
            st.insert(head);
            head = head->next;
        }
    }
    return false;
}

思路2：双指针。
如果链表存在环，则快指针和慢指针一定会相遇。

bool hasCycle(ListNode *head) {
    ListNode *slow, *fast;
    slow = fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) return true;
    }
    return false;
}

142.环形链表 II

分析相遇时的情况：

从起点到环入口的路程记做a，环的长度记做b；
快指针走的路程记做f，慢指针走的路程记做s；
我们可以得到：
f = s + nb
f = 2s
  => s = nb  
  => s+a = 0+a

所以：当快慢指针相遇时，让头指针和慢指针同时开始走，它们相遇的点就是环的入口。

ListNode *detectCycle(ListNode *head) {
    ListNode *slow, *fast;
    slow = fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    // 没有环
    if (!fast || !fast->next) return NULL;
    // 有环
    while (head != slow) {
        head = head->next;
        slow = slow->next;
    }
    return head;
}

876.链表的中间结点

题目描述：如果有两个中间结点，则返回第二个中间结点。

该问题常常是以后题目的子问题。注意两点：

快慢指针一起出发
判断条件(fast && fast->next)

ListNode* middleNode(ListNode* head) {
    ListNode *slow, *fast;
    slow = fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

剑指 Offer 22. 链表中倒数第k个节点

假设 k 不会超过链表⻓度

ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode *slow, *fast;
    slow = fast = head;
    
    while (k--) fast = fast->next;
    
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

704.二分查找

数组是升序的

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target)
            return mid;
        else if(nums[mid] < target)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

167.两数之和 II - 输入有序数组

vector<int> twoSum(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l < r) {
        int sum = nums[l] + nums[r];
        if (sum == target)
            return {l, r};
        else if (sum < target)
            l++;
        else
            r--;
    }
    return {};
}

15.三数之和

题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

思路：

固定一个数，对剩下的数组使用双指针进行查找。
注意去重操作。

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    if (nums.size()<3) return ans;
    
    sort(nums.begin(), nums.end());
    for (int i=0; i<nums.size()-2; i++) {
        // 去重
        if (i>0 && nums[i] == nums[i-1]) {
            continue;
        }
        int l = i+1, r = nums.size()-1;
        int val = 0 - nums[i];
        while (l < r) {
            int temp = nums[l] + nums[r];
            if (temp == val) {
                vector<int> t = {nums[i], nums[l], nums[r]};
                ans.push_back(t);
                // 去重
                while (l<r && nums[l] == nums[l+1]) {
                    l++;
                }
                l++;
                // 去重
                while (l<r && nums[r] == nums[r-1]) {
                    r--;
                }
                r--;
            }else if (temp < val){
                l++;
            }else{
                r--;
            }
        }
    }
    return ans;
}

11.盛最多水的容器

左右哪边小哪边往中间移动

int maxArea(vector<int>& height) {
    int i = 0, j = height.size()-1;
    int maxArea = 0;

    while (i < j) {
        int temp = min(height[i],height[j]) * (j-i);
        maxArea = max(temp, maxArea);

        if (height[i] > height[j]) {
            j--;
        }else{
            i++;
        }
    }
    return maxArea;
}

两个数组的交集 II

题目要求：结果中的元素应与在两个数组中出现的次数一致。
思路：先排序再双指针。

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    vector<int> ans;
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    
    int p1 = 0, p2 = 0;
    int l1 = nums1.size(), l2 = nums2.size();
    while (p1 < l1 && p2 < l2) {
        int a = nums1[p1], b = nums2[p2];
        if (a == b) {
            ans.push_back(a);
            p1++; p2++;
        }else{
            a<b ? p1++ : p2++;
        }
    }
    return ans;
}

209.长度最小的子数组

题目描述：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

思路：因为是求连续子数组，所以可以用滑动窗口的方法。

1.不断扩张窗口，寻找一个可行解；
2.不断收缩窗口，优化这个可行解，直到不满足条件；
3.重复1、2，即寻找下一个可行解，然后再优化。

int minSubArrayLen(int s, vector<int>& nums) {
    int lens = nums.size();
    if (lens==0) return 0;
    
    int l = 0, r = l;
    int sum = 0, ans = INT_MAX;
    while (r < lens) {
        sum += nums[r];
        r++;
        
        while (sum >= s) {
            ans = min(ans, r-l);
            sum -= nums[l];
            l++;
        }
    }
    // 考虑sum(nums)<s的情况
    return ans==INT_MAX ? 0: ans;
}

76.最小覆盖子串

思路：和上题滑动窗口的思路一样。只是判断条件麻烦了点。

如何判断当前窗口包含T中的所有字符？

⽤⼀个哈希表 needs 记录t中包含的字符及次数；
⽤另⼀个哈希表 window 记录当前窗⼝中包含的t中的字符及次数。

使用一个变量 match 保存 window 满足 needs 的个数，如果 match 等于 needs，则当前窗口满足条件。

string minWindow(string s, string t) {
    int start = 0, minLen = INT_MAX;
    int l = 0, r = 0;
    
    unordered_map<char, int> needs;
    unordered_map<char, int> windows;
    for (char c: t) needs[c]++;
    
    int match = 0;
    while (r < s.size()) {
        // 不断扩大窗口
        char c1 = s[r];
        if (needs.count(c1)) {
            windows[c1]++;
            if (windows[c1] == needs[c1]) {
                match++;
            }
        }
        r++;
        
        // 如果窗口符合条件，不断收缩窗口
        while (match == needs.size()) {
            if (r - l < minLen) {
                minLen = r - l;
                start = l;
            }
            
            char c2 = s[l];
            if (needs.count(c2)) {
                windows[c2]--;
                if (windows[c2] < needs[c2]) {
                    match--;
                }
            }
            l++;
        }
    }
    return minLen == INT_MAX ? 0: s.substr(start, minLen);
}

3.无重复字符的最长子串

思路：

1.扩大窗口，寻找最长的子串
2.如果遇到重复的情况，缩小子串，直到满足条件
3.重复1、2，直到最后。

int lengthOfLongestSubstring(string s) {
    int l = 0, r = l;
    int ans = 0;
    unordered_map<char, int> map;
    while (r < s.size()) {
        char c1 = s[r];
        map[c1]++;
        r++;
        
        while (map[c1] > 1) {
            char c2 = s[l];
            map[c2]--;
            l++;
        }
        ans = max(ans, r-l);
    }
    return ans;
}

剑指 Offer 57 - II. 和为s的连续正数序列

题目描述：
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例：

输入：target = 9
输出：[[2,3,4],[4,5]]

vector<vector<int>> findContinuousSequence(int target) {
    vector<vector<int>> ans;
    int l = 1, r = l;
    int sum = 0;
    while (r < target) {
        sum += r;

        while (sum >= target) {
            if (sum == target && r-l+1 >= 2) {
                vector<int> temp;
                for (int i=l; i<=r; i++) {
                    temp.push_back(i);
                }
                ans.push_back(temp);
            }
            sum -= l;
            l++;
        }
        r++;
    }
    return ans;
}