力扣-双指针1

何为双指针

双指针指向同一数组，然后配合着进行搜索等活动。

滑动窗口的时候很好使用。

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

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

题目

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：

2 <= numbers.length <= 3 *
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

题解

判断两数之和是否等于target值。可以使用遍历。一般做法是通过确定第一个数，然后进行后续的遍历。但是这里有一个前提调节，numbers是有序数组。因此这里可以考虑使用双指针来解决问题。

让一个指针指向开头，一个指向结尾。如果相加比target小，那么指向开头的指针往后移，如果比target大，那就指向结尾的指针往前移。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n=numbers.size();
        int start=0,end=n-1;
        int i;
        while(numbers[start]+numbers[end]!=target){
            if(numbers[start]+numbers[end]>target)
                end--;
            else
                start++;
        }
        return vector<int>{start+1,end+1};
    }
};

88.合并两个有序数组

88. 合并两个有序数组

题目

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
<= nums1[i], nums2[j] <=

题解

合并两个有序数组，且合并的时候不新建一个新的数组，直接修改nums1数组。

因为nums1数组本身空间就是m+n，这个时候后面的n为0.

因此我们可以从nums1和nums2中非零的位置开始，置为指针。

比较越大的放在越后面，所以这里还需要一个pos指向nums1的最后。

这样子就可以实现数组的合并。

在这里需要注意一个点，当m或者n已经为0时，就不需要比较了。因为nums1本来就在nums1上，因此不需要继续赋值。如果n>0，那么就把nums2中的数复制过去。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int pos=m+n-1;
        m=m-1;
        n=n-1;
        while(m>=0&&n>=0){
            if(nums1[m]>nums2[n])
                nums1[pos--]=nums1[m--];
            else
                nums1[pos--]=nums2[n--];
        }
        
        while(n>=0&&pos>=0){
            nums1[pos--]=nums2[n--];
        }
    }
};

142.环形链表Ⅱ

142. 环形链表 II

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：

链表中节点的数目范围在范围 [0, 104] 内
<= Node.val <=
pos 的值为 -1 或者链表中的一个有效索引

题解

补充一个知识

快慢指针（Floyd 判圈法）
对于链表找环路的问题，有一个通用的解法——快慢指（Floyd 判圈法）。

给定两个指针，分别命名为slow 和fast，起始位置在链表的开头。每次fast 前进两步，slow 前进一步。如果fast可以走到尽头，那么说明没有环路；如果fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻slow 和fast 相遇。

当slow 和fast 第一次相遇时，我们将fast 重新移动到链表开头，并让slow 和fast 每次都前进一步。当slow 和fast 第二次相遇时，相遇的节点即为环路的开始点。

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

76.最小覆盖子串

76. 最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：

m == s.length
n == t.length
1 <= m, n <=
s 和 t 由英文字母组成

题解

求S的最小子串，该子串只需要含有T中的字母就可以，不需要按顺序。

在这里我们首先可以申请两个标记数组，用来获取字符串t的字符和个数。
    vector<int> words(128,0);
        vector<bool> flag(128,false);
        int i=0;
        for(i=0;i<t.size();i++){
            words[t[i]]++;
            flag[t[i]]=true;
        }
接着定义几个变量，一个是左右指针，还有一个是最小的长度以及最小字符串开始的位置。

首先是左指针不动，指向第一个位置。接着，右指针遍历，并且判断该字符是否是t中有的，如果有，个数减一，count++。直到count跟t一样长。这个时候我们就找到了一个字符串，包含t。但是不一定是最短的。这个时候我们就开始移动左指针。在移动的时候要判断，如果第一个位置是t中的，那么也要同步发生变化。
class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> words(128,0);
        vector<bool> flag(128,false);
        int i=0;
        for(i=0;i<t.size();i++){
            words[t[i]]++;
            flag[t[i]]=true;
        }
        int l=0,r=0;
        int min_size=s.size()+1;
        int min_l=0,count=0;
        for(r=0;r<s.size();r++){
            if(flag[s[r]]==true){
                if(--words[s[r]]>=0){
                    count++;
                }
                while(count==t.size()){
                    if(r-l+1<min_size){
                        min_l=l;
                        min_size=r-l+1;
                    }
                    if(flag[s[l]]==true&&++words[s[l]]>0){
                        count--;
                    }
                    l++;
                }
            }
        }
        return min_size>s.size()?"":s.substr(min_l,min_size);
    }
};