C++ 双指针汇总(快慢指针, 滑动窗口, 前后指针,左右指针)

妖狐艹你老母 2023-01-09 14:28 198阅读 0赞

# 一. 归并有序序列 #

LeetCode 88题

input: 	nums1 = {2,2,3,0,0,0}; m=3;  nums2 = {1,5,6}; n=3
    output: nums1 = {1,2,2,3,5,6}
    require: 时间O(n) 内存O(1)

## 1.1 总结: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]

## 1.2 代码 ##

#include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <map>
    
    using namespace std;
    
    // 归并两个有序数组
    // 加上&参数传递的是地址, 这样就可以改变参数的值, 因为题目要求是在数组nums1上进行排序
    void solution(vector<int>& nums1, int m, std::vector<int> nums2, int n){ 
    	for(auto i: nums1)cout<<i<<" "; cout<<endl;
    	int pos=nums1.size()-1;// 这里也可以是m+n-1
    	m--;
    	n--;
    	while(m>=0 && n>=0){ 
    		nums1[pos--] = nums1[m] <= nums2[n] ? nums2[n--]:nums1[m--];
    	}
    	while(n>=0){  
    	//这里是因为如果num1还有剩余, 那么num1前面的因为已经排好序那自然是没毛病了, 
    	// 但是num2还有剩余, 就需要转移到num1中
    		nums1[pos--] = nums2[n--];
    	}
    }
    
    
    
    int main(int argc, char const *argv[])
    { 
    	std::vector<int> nums1 = { 2,2,3,0,0,0};
    	std::vector<int> nums2 = { 1,5,6};
    
    	solution(nums1, 3, nums2, 3);
    	for(auto i: nums1)cout<<i<<" "; cout<<endl;
    	printf("%s\n", "hello");
    	return 0;
    }

# 二. 两数之和 #

LeetCode 167题

input: 	nums1 = {1,2,3,4,5,7}; target=9

## 2.1 总结: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 1]

## 2.2 代码 ##

#include<iostream>
    #include<algorithm>
    #include<vector>
    #include<stdio.h>
    #include <map>
    
    using namespace std;
    void print_vector(vector<int> numbers){ 
        for(auto c : numbers) cout<< c <<" ";cout<<endl;
    }
    
    // 使用&, 指的是函数参数传递进来的可以被改变,引用传递, int a, func(a) func(int &a){a=100}
    // 使用*, 指的是参数即为指针, int a, func(&a) func(int *a){*a=100}
    int solution1(vector<int> numbers, int target){ 
        print_vector(numbers);
        sort(numbers.begin(), numbers.end());
        int sum, i=0,j=numbers.size()-1;
        while (i<j){ 
            sum= numbers[i]+numbers[j];
            if (sum>target) { j--; }
            else if(sum==target) { break; }
            else { i++;}
        }
        print_vector(numbers);
        printf("%d = %d+%d\n", target, numbers[i], numbers[j]);
    }
    
    // 也可以做一个字典, 字典只需要遍历一遍即可, 不需要排序, 而双指针需要排序, 相当于遍历两遍
    void solution2(vector<int> numbers, int target){ 
        map<int,int> personnel;
        for(int i=0; i<numbers.size(); i++){ 
            int sum = target-numbers[i];
            if (personnel.find(sum) == personnel.end()){ 
                personnel.insert(pair<int, int>(numbers[i],i));
            }else{ 
                printf("%d = %d+%d\n", target, numbers[i], personnel.find(sum)->first);
            }
        }
    }
    // python解法
    // numbers = [1,2,4,5,7]
    // target = 9
    
    // map1 = {}
    // for i,numb in enumerate(numbers):
    // if map1.get(target-numb)==None:
    // map1[numb] = i
    // else:
    // print(numb, target-numb)
    
    
    int main(int argc, char const *argv[])
    { 
        vector<int>numbers = { 2,7,11,15,1,2};
    
        solution1(numbers, 9);
        solution2(numbers, 9);
        cout<<"hello" <<endl;
        return 0;
    }

# 三. Floyd算法 #

LeetCode 142题

*  给定一个链表, 判断是否存在环路, 存在则返回环路入口节点  
    ![在这里插入图片描述][20210116151506373.png]  
    找到2的所属节点

总结: 这题太重要了, 一个**Floyd算法**的数学证明和**单链表**的各种基础操作

## 3.1 总结 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 2]

## 3.2 代码 ##

注意: 这里包含单链表的基础操作

#include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct ListNode { 
    	int val;
    	ListNode *next;
    	ListNode(int x) : val(x), next(nullptr) { } // 这里默认Node的next是nullptr
    };
    
    
    // Floyd算法, 找到环路起点
    ListNode *detectCycle(ListNode *head){ 
    	ListNode *slow=head;
    	ListNode *fast=head;
    	int i=20;
    	// fast:slow=2:1的速度前进, 如果fast到达终点, 则没有环路, 
    	// 否则等二者相遇, fast回归起点, 1:1速度进行,二次相遇后, 为起始点
    	while(fast && fast->next){ 
    		fast = fast->next->next; //因为while入口已经确定fast->next存在, 那么fast->next的next至少至少也是nullptr格式, 因为结构体定义部分定义的, 所以这里fast->next->next;不会越界
    		slow = slow->next;
    		if(fast == slow){  //第一次相遇
    			fast = head;
    			while(fast!=slow){ 
    				slow = slow->next;
    				fast = fast->next;
    			}
    			cout<<"\n带环最终结果是"<<fast->val<<endl;
    			return fast; //第二次相遇
    		}
    	}
    	cout<<"没有环"<<endl;
    	return nullptr;
    }
    
    int main(int argc, char const *argv[])
    { 
    	ListNode *head, *end; //创建两个节点
    	head=(ListNode*)malloc(sizeof(ListNode)); //给头节点先开辟个空间
    
    	// 创建节点,并赋值
    	ListNode *normal=(ListNode*)malloc(sizeof(ListNode)); //创建临时节点
    	normal->val = 28; //给临时节点赋值
    	head->next = normal; //临时节点链接到头节点
    	end = head->next;  
    	for(int i=0; i<11; i++){  //链表的插入
    		ListNode *a=(ListNode*)malloc(sizeof(ListNode));
    		a->val = i;
    		end->next = a;
    		end = end->next;
    		// cout<<end->val<< endl;
    	}
    	
    
    	cout<<"打印当前链表内容: 0 28 0 1 2 3 4 5 6 7 8 9"<<endl;
    	detectCycle(head);
    
    	end->next = normal; // 加上一个圆环
    
    	ListNode *a = head;
    	cout<<"打印一下带环链表内容,"<<endl;
    	for(int i=0; i<20; i++){ 
    		cout<<a->val<<" ";
    		a = a->next;
    	}
    
    	detectCycle(head);
    	cout<<"hello" <<endl;
    	return 0;
    }

# 四. 最长不重复子串(滑动窗口) #

LeetCode 3题

input  = 'acbva'
    output = "acbv"或者"cbva"
    output = 4
    
    最长不重复子串解题技巧: 
    设定左右两指针, 指向窗口找最大
    如若窗口有重复, 集合删左左在进

## 4.1 总结 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 3]

## 4.2 代码 ##

注意这里使用一个字典, 集合, 列表其实都可以, 只要能判定元素是否在列表中, 能删除列表的第一位即可

#include <vector>
    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <set>
    using namespace std;
    
    // 问题描述: 
    // 不重复最长子串
    // 输入 'acbva'
    // 找到这串里面最长的不重复的子串, 如果是acbva, 这是子序列, 
    // 只有不重复的才是子串, 则acbv是子串, acbv或者cbva是不重复最长子串
    
    // -----------解题关键: 就是创建一个数组, 集合, 字典, 用来装窗口内是否有重复, 
    // -------------如果有重复就左指针右移, 没有就右右移
    
    // 最长不重复子串解题技巧: 
    // 设定左右两指针, 指向窗口找最大
    // 如若窗口有重复, 集合删左左在进
    string solution_set(string s){  //acbva
    	cout << "\n需要找的最长子串是"<<s<<endl;
    	set<char> set_swap;
    	int max_len = 0;
    	int left=0, right=0;
    	while(right<s.size()){ 
    		// set_swap保存的是s[left, right]不重复的数据呀
    		if(0 == set_swap.count(s[right])){  // 确定没s[right], 就是加入s[right]依然没有重复的, 则将s[right]加入到字典, 
    			set_swap.insert(s[right++]);
    			if(max_len < right-left){ 
    				for(set<char>::iterator iter = set_swap.begin(); iter!=set_swap.end(); iter++){ 
    					cout<<*iter<<" ";
    				}cout<<endl;				
    			}
    			max_len = max(max_len, right-left);
    		}
    		else{  // 如果有重复的, 那就删除
    			set_swap.erase(s[left++]);
    		}
    	}
    	printf("最长子串是: %d\n", max_len);
    	string res = "";
    	return res;
    }
    
    string solution_vector(string s){ 
    	string res = "";
    	std::vector<char> v_swap;
    	std::vector<string> v_res;
    	int left=0, right=0, max_len=0;
    	while(right < s.size()){ 
    		if (0 == std::count(v_swap.begin(), v_swap.end(), s[right])){ 
    			v_swap.push_back(s[right++]);
    			if (max_len<right-left){  // 打印结果
    				for(auto i:v_swap){ 
    					cout<<i<<" ";
    				}cout<<endl;
    			}
    			max_len = max(max_len, right-left);
    		}
    		else{ 
    			v_swap.erase(v_swap.begin(),v_swap.begin()+1); // 删除列表中的第一个
    			left++;
    		}
    	}
    	cout<<"输入"<<s<<" 结果是:"<<max_len<<endl;
    	return res;
    }
    
    int main(int argc, char const *argv[])
    { 
    	string s = "11334566";
    	string res = solution_set(s);
    	// string res = solution_vector(s);
    	cout<< "hello world" <<endl;
    	return 0;
    }

# 五. 最短覆盖子串(滑动窗口) #

LeetCode 76题

input:   S = "ADOBECODEBANC";  T = "ABC";
    output:  res = BANC

## 5.1 总结 ##

这里需要注意的是:  
创建一个能够统计目标字符的字典, 这样就可以在每次判断每一个字符是否是多余的, 对窗口去冗余极其重要  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 4]

## 5.2 代码 ##

### a. python实现 ###

import sys,os
    # 核心思路: 找到目标窗口, 然后去除冗余, 完成
    # 右指针向右, 直到遇到全部T,
    # 左指针向右, 直到最短子串S1出现, 给临时最优
    # 左指针在向右, 此时窗口没有目标子串, 此时右指针向右,右指针 
    # 
    # 最短目标子串解题技巧: 
    # 设定左右两指针, 指向窗口找目标
    # 窗有冗余左进右, 无余左进等右尽
    # 
    # 注意滑动窗口就是目标值
    def solution(S, T):
        # print(S, T)
        if len(S)<len(T):
            return ""
        window = "" 
        result = ""
        need = { }
        for _ in T:need[_] = 1 if _ not in need else need[_]+1
        needCnt = len(T)
        for c in S:
            if c in need:
                if need[c]>0:
                    needCnt-=1
                need[c]-=1
            window+=c
            if needCnt == 0: # 窗口已经满足, 可以去冗余, 这个时候, need里面的值, 有可能是-2, 如AAABC
                while True:
                    if window[0] in T: # 窗口最左是目标字符
                        if need[window[0]] <0: # 字符没用, 左指针右移
                            need[window[0]] += 1
                            window = window[1:]
                        elif need[window[0]] == 0: # 关键 表示正好, 此时左右没有冗余, 此时左指针向右移动一个后, 整个窗口就不完整了, 进行下一轮
                            if result:
                                if len(window)<len(result):
                                    result = window 
                            else:
                                result = window
                            need[window[0]] += 1
                            window = window[1:]
                            needCnt += 1
                            break
                    else: # 这里是最左的字符是垃圾, 直接去掉即可
                        window = window[1:]
        print("结果是: ",result)
        return result
    
    if __name__ == '__main__':
        solution("ADOBECODEBANC", "ABC")
    # // Input: S = "ADOBECODEBANC", T = "ABC"
    # // Output: "BANC"

### b. C++实现 ###

#include <iostream>
    #include <algorithm>
    #include <stdio.h>
    #include <vector>
    #include <sstream> // 为了使用stringsteam
    using namespace std;
    
    
    // 题目描述: 给定字符串S,T, 求S中包含T所有字符的最短连续子字符串的长度, 时间复杂度不能超过O(n)
    // 输入样例: 
    // Input: S = "ADOBECODEBANC", T = "ABC"
    // Output: "BANC"
    
    
    // 解题思路: 双指针(前后指针)指向开始, 如果没有遇到T中的字符串, 
    // 双指针同时向后移动, 遇到一个以后, 后指针继续, 知道遇到全部T, 
    // 将当前前后指针指向子串给临时最优, 
    // 核心: 当窗口不满足要求的时候, 就向右拓宽边界
    string solution(string S, string T){ 
    	cout<<S<<"里面找"<<T<<endl;
    	vector<int> chars(128, 0);     //计数需要查找的字符个数, 比如AABBA 则需要找到三个A两个B
    	vector<bool> flag(128, false); //标记都有哪几个字符需要查找
    	// 先统计T中的字符情况
    	for(int i = 0; i < T.size(); ++i) { 
    		flag[T[i]] = true;
    		++chars[T[i]];
    	}
    
    	// 移动滑动窗口，不断更改统计数据
    	int cnt = 0, left = 0, min_l = 0, min_size = S.size() + 1;
    	for (int right = 0; right < S.size(); ++right) { 
    		if (flag[S[right]]) {  // 如果当前right所指字符是待查找字符
    			if (--chars[S[right]] >= 0) {  // 且当前该字符还没查完, 那就计数加
    				++cnt;
    			}
    			// 若目前滑动窗口已包含T中全部字符，
    			// 则尝试将l右移，在不影响结果的情况下获得最短子字符串
    			while (cnt == T.size()) { 
    				if (right - left + 1 < min_size) {  // 缩短长度
    					min_l = left;
    					min_size = right - left + 1;
    				}
    				if (flag[S[left]] && ++chars[S[left]] > 0) { 
    					--cnt;
    				}
    				++left;
    			}
    		}
    	}
    	return min_size > S.size()? "": S.substr(min_l, min_size);
    }
    int main(int argc, char const *argv[])
    { 
    	string S = "ADOBECODEBANC";
    	string T = "ABC";
    	string res = solution(S,T);
    	cout << res << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70]: /images/20221119/8d53892fa9244dbb881e36bb5c602275.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 1]: /images/20221119/5967f276a15e461093cc1e23651cb8eb.png
[20210116151506373.png]: /images/20221119/99812da2650745a887843e951a40b62a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 2]: /images/20221119/bc3d0032ae774846994fef4af172b03e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 3]: /images/20221119/6e0025ce455b4ab19c23db785503b3f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDYwODE5_size_16_color_FFFFFF_t_70 4]: /images/20221119/e07717fa4f734376aace22298accd14b.png