双指针

loop detection

• Method 1: hash table

  unordered_set<node*> visited;
  

• Method 2: fast-slow pointer

  O(1) Space.

  fast一次走两格，slow一次走一格；两指针相遇则说明有环。

  若要找到环头，则相遇之后再从起点跑一个指针，此指针与slow指针相遇时即到达环头。

有序数组中的搜索

两数之和

给定一个数组，求其中所有不重复的两个数，使其和为特定值。

// O(n), lr pointer
vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());

    vector<vector<int>> res;

    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int sum = nums[l] + nums[r];
        int left = nums[l], right = nums[r];
        if (sum < target) {
            while (l < r && nums[l] == left) l++;
        } else if (sum > target) {
            while (l < r && nums[r] == right) r--;
        } else {
            res.push_back({left, right});
            while (l < r && nums[l] == left) l++;
            while (l < r && nums[r] == right) r--;
        }
    }

    return res;
}


// 如果只需要求一组这样的数据（的下标），也可以使用hash
// 但hash法求所有时不好去重复，故不推荐。
// O(n), hash
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> v;
    for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];
        if (v.count(target - x)) return vector<int>{i, v[target - x]};
        else v[x] = i;
    }
    return vector<int>{-1, -1}; // never reach here
}

三数之和

给定一个数组，求其中所有不重复的三个数，使其和为0。

// O(n^2), lr pointer
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

合法三角形个数

给定一个边长数组，求其中可以组成合法三角形的三元组个数。

暴力枚举三条边\(O(N^3)\)；排序后枚举两条边，二分第三条边\(O(N^2\log N)\)。

排序后枚举一条边，双指针处理另外两条边\(O(N^2)\)。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            // double pointer (j, k)
            for (int j = i + 1, k = i + 1; j < nums.size(); j++) {
                // j and k both only takes at most N ++step
                while (k + 1 < nums.size() && nums[k + 1] < nums[i] + nums[j]) k++;
                ans += max(k - j, 0);
            }
        }
        return ans;
    }
};

链表相交点

双指针换家。证明很简单，但是方法想不到啊。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode *a = headA, *b = headB;
        while (a != b) {
            if (a) a = a->next; else a = headB;
            if (b) b = b->next; else b = headA;
        }
        return a;
    }
};

救生艇的最少数量

并不是动规，问的是袋子的最少数量。

应该用贪心法做，每次尽可能填满袋子（先塞大的，然后用小的开始填）。

进一步可以用双指针实现这个过程。

每艘船载人量上限为2：

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        // greedy, double pointer
        sort(people.begin(), people.end());
        int l = 0, r = people.size() - 1;
        int ans = 0;
        while (l <= r) {
            int rem = limit - people[r];
            if (l < r && rem >= people[l]) {
                rem -= people[l];
                l++;
            }
            ans++;
            r--;
        }
        return ans;
    }
};

每艘船载人量任意的情况：

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        // greedy, double pointer
        sort(people.begin(), people.end());
        int l = 0, r = people.size() - 1;
        int ans = 0;
        while (l <= r) {
            int rem = limit - people[r];
            // change to while !
            while (l < r && rem >= people[l]) {
                rem -= people[l];
                l++;
            }
            ans++;
            r--;
        }
        return ans;
    }
};

和为s的连续正整数序列

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

两个指针都从首部开始。

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int l = 1, r = 2;
        vector<vector<int>> ans;
        while (l < r && r <= (target + 1) / 2) {
            int s = (l + r) * (r - l + 1) / 2;
            if (s == target) {
                vector<int> tmp;
                for (int i = l; i <= r; i++) tmp.push_back(i);
                ans.push_back(tmp);
                l++; // don't forget this.
            }
            else if (s < target) r++;
            else l++;
        }
        return ans;
    }
};