雙指針是在陣列處理時可以利用的技巧，利用兩個指針去做判斷或是構造出窗口幫助解題，根據兩個指針的特性可以分為對撞指針、快慢指針以及滑動窗口。

對撞指針

兩個指針在數列兩端，移動方向相反，向中間移動，通常終止條件為兩指針對撞 or 滿足題目需求，兩邊指針的移動條件則要視題目需求做判斷。

LeetCode 167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.Your solution must use only constant extra space.

Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while(left < right){
            if(numbers[left] + numbers[right] > target) right--;
            else if(numbers[left] + numbers[right] < target) left++;
            else break;
        }
        return {left + 1, right + 1};
    }
};

因為題目提供的數列已經經過排序，因此可以透過 left 和 right 指針代表的數字和來判斷是否做指針的移動，當總和小於 target 時，將 left 右移可以使總和變大；反之將 right 左移可以使總和變小，直到總和等於 target 時結束。

LeetCode 11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.Return the maximum amount of water a container can store.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ans = 0;
        while(left < right){
            ans = max(ans, (right -  left) * min(height[left], height[right]));
            if(height[left] < height[right]) left ++;
            else right--;
        }
        return ans;
    }
};

容器的高度是由左右兩短較短的一邊決定，因此在移動左右指針時，若移動較長邊只有可能使容量變小 or 不變，為了要算出當前的最大容量，必須移動兩邊中較短者，並將容量與之前的最大值比較，直到兩指針相撞。

快慢指針

兩個指針初始位置相同，移動方向相同，但速度不同，通常終止條件為兩指針再次相遇 or 快指針移動至數列尾端，兩邊指針的移動條件則要視題目需求做判斷。

LeetCode 26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

  1. Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
  2. Return k.

Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]

Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(nums[slow] != nums[fast]){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }
};

慢指針 slow 代表了未重複的數列的結尾，並利用快指針 fast 來遍歷整個數列，當快慢指針值不同時，代表該數字尚未加入未重複數列中，將其加入並且把 slow++，迴圈執行至快指針到達數列尾端。

Solution 2:

1
2
3
4
5
6
7
8
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        set<int> s(nums.begin(),nums.end());
        copy(s.begin(),s.end(),nums.begin());
        return s.size();
    }
};

當然這題也可以直接用 set 不重複的特性來解決…

LeetCode 141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true

Example 2:

Input: head = [1,2], pos = 0
Output: true

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }
};

快指針一次動兩步，慢指針則只動一步，如果存在環則快指針一定會碰到慢指針，因此回傳 true，否則迴圈在快指針到達尾端時停止並回傳 false。

滑動窗口

兩個指針初始位置相同，移動方向相同，但移動條件不同 (一般為滿足條件時左指針向右，窗口縮小；不滿足時右指針向右，窗口擴大)，通常終止條件為右指針移動至數列尾端。

LeetCode 209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sum = 0, ans = 100001;
        while(right < nums.size()){
            sum += nums[right];
            while(sum >= target){
                ans = min(ans, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        if(ans == 100001) ans = 0;
        return ans;
    }
};

因為題目有限制原始陣列的大小，因此可以先令 ans 為大小上限 +1 ，之後利用滑動窗口的方式，每次滿足 sum >= target 時做比較，最後如果 ans 和原始值相同，代表無法滿足條件，回傳 0。

LeetCode 904. Fruit Into Baskets

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

  1. You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
  2. Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
  3. Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:
Input: fruits = [1,2,1]
Output: 3

Example 2:
Input: fruits = [0,1,2,2]
Output: 3

Example 3:
Input: fruits = [1,2,3,2,2]
Output: 4

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0, right = 0, ans = 0;
        unordered_map<int,int> map;
        while(right < fruits.size()){
            map[fruits[right]]++;
            while(map.size() > 2){
                int fruit = fruits[left++];
                if((--map[fruit]) == 0) map.erase(fruit);
            }
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

利用 unordered_map 來儲存窗口內水果的種類和數量，如果 size > 2 代表超出數量，因此縮減窗口直到滿足條件，並且將水果數量與 ans 做比較。