雙指針 - 簡書

一茂缚、雙指針總結(jié)

1.1題目

快慢指針（主要解決鏈表中的問題）

141.環(huán)形鏈表
142.環(huán)形鏈表 II
876.鏈表的中間結(jié)點
劍指 Offer 22. 鏈表中倒數(shù)第k個節(jié)點

左右指針

704.二分查找
167.兩數(shù)之和 II - 輸入有序數(shù)組
15.三數(shù)之和（去重）
11.盛最多水的容器

滑動窗口（兩個指針從一個起點出發(fā)）

209.長度最小的子數(shù)組
76.最小覆蓋子串（hard）
3.無重復(fù)字符的最長子串
劍指 Offer 57 - II. 和為s的連續(xù)正數(shù)序列

1.2滑動窗口的思路

1.不斷擴張窗口，尋找一個可行解蕾哟；
2.不斷收縮窗口则披，優(yōu)化這個可行解共缕，直到不滿足條件；
3.重復(fù)1士复、2图谷，即尋找下一個可行解，然后再優(yōu)化阱洪。

（適用于求最小的問題便贵，求最大的問題要改一下，不過代碼結(jié)構(gòu)差不多）

int left = 0, right = 0;

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

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

稍微?煩的地?就是這個 valid 條件冗荸。

二承璃、題目

141.環(huán)形鏈表

思路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：雙指針。
如果鏈表存在環(huán)蚌本，則快指針和慢指針一定會相遇盔粹。

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.環(huán)形鏈表 II

分析相遇時的情況：

從起點到環(huán)入口的路程記做a，環(huán)的長度記做b程癌；
快指針走的路程記做f舷嗡，慢指針走的路程記做s；
我們可以得到：
f = s + nb
f = 2s
  => s = nb  
  => s+a = 0+a

所以：當(dāng)快慢指針相遇時嵌莉，讓頭指針和慢指針同時開始走进萄，它們相遇的點就是環(huán)的入口。

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;
    }
    // 沒有環(huán)
    if (!fast || !fast->next) return NULL;
    // 有環(huán)
    while (head != slow) {
        head = head->next;
        slow = slow->next;
    }
    return head;
}

876.鏈表的中間結(jié)點

題目描述：如果有兩個中間結(jié)點，則返回第二個中間結(jié)點中鼠。

該問題常常是以后題目的子問題可婶。注意兩點：

快慢指針一起出發(fā)
判斷條件(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. 鏈表中倒數(shù)第k個節(jié)點

假設(shè) 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.二分查找

數(shù)組是升序的

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.兩數(shù)之和 II - 輸入有序數(shù)組

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.三數(shù)之和

題目描述：給你一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a兜蠕，b扰肌，c 抛寝，使得 a + b + c = 0 熊杨？請你找出所有滿足條件且不重復(fù)的三元組。

思路：

固定一個數(shù)盗舰，對剩下的數(shù)組使用雙指針進行查找晶府。
注意去重操作。

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;
}

兩個數(shù)組的交集 II

題目要求：結(jié)果中的元素應(yīng)與在兩個數(shù)組中出現(xiàn)的次數(shù)一致钻趋。
思路：先排序再雙指針川陆。

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.長度最小的子數(shù)組

題目描述：給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組蛮位，并返回其長度较沪。如果不存在符合條件的子數(shù)組，返回 0失仁。

思路：因為是求連續(xù)子數(shù)組尸曼，所以可以用滑動窗口的方法。

1.不斷擴張窗口萄焦，尋找一個可行解控轿；
2.不斷收縮窗口，優(yōu)化這個可行解拂封，直到不滿足條件茬射；
3.重復(fù)1、2冒签，即尋找下一個可行解在抛，然后再優(yōu)化。

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.最小覆蓋子串

思路：和上題滑動窗口的思路一樣萧恕。只是判斷條件麻煩了點刚梭。

如何判斷當(dāng)前窗口包含T中的所有字符？

??個哈希表 needs 記錄t中包含的字符及次數(shù)廊鸥；
?另?個哈希表 window 記錄當(dāng)前窗?中包含的t中的字符及次數(shù)望浩。

使用一個變量 match 保存 window 滿足 needs 的個數(shù)，如果 match 等于 needs惰说，則當(dāng)前窗口滿足條件磨德。

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.無重復(fù)字符的最長子串

思路：

1.擴大窗口，尋找最長的子串
2.如果遇到重復(fù)的情況典挑，縮小子串酥宴，直到滿足條件
3.重復(fù)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的連續(xù)正數(shù)序列

題目描述：
輸入一個正整數(shù) target ，輸出所有和為 target 的連續(xù)正整數(shù)序列（至少含有兩個數(shù)）琳水。
序列內(nèi)的數(shù)字由小到大排列肆糕，不同序列按照首個數(shù)字從小到大排列。

示例：

輸入：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;
}