Double Pointer

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

Two Sum

Input array is sorted (Easy)

题目描述

　　在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。

输入输出样例

　　输入是一个数组和一个给定值。输出是两个数的位置，从１开始计数。

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

c++:

vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size() - 1, sum;
    while (l < r) {
        sum = numbers[l] + numbers[r];
	if (sum == target) break;
	if (sum < target) ++l;
 	else --r;
    }
    return vector<int>{l + 1, r + 1};

java:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] indexs = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            if ((numbers[left] + numbers[right]) == target) {
                indexs[0] = left + 1;
                indexs[1] = right + 1;
                break;
            } else if ((numbers[left] + numbers[right]) > target) {
                right--;
            } else {
                left++;
            }
        }
        return indexs;
    }
}

归并两个有序数组

Merge Sorted Array (Easy)

题目描述

　　给定两个有序数组，把两个合并成一个。

输入输出样例

　　输入是两个数组和他们分别的长度m和n。其中第一个数组的长度被延长至m+n,多出的n位被0填充。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间。

1 2	Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2, 5, 6], n = 3 Output: nums1 = [1,2,2,3,5,6]

c++:

void merge(vector<int>& nums1, vector<int>& nums2, int m, int n) {
    int pos = m-- + n-- - 1;
    while (m >= 0 && n >= 0) {
        nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
    }
    while (n >=0) {
        nums1[pos--] = num2[n--];
    }
}

java:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len = m + n;
        for (int i = len - 1; i >= 0; i--) {
            if (m == 0 && n == 0) {
                return;
            }
            if (n <= 0 && m > 0) {
                nums1[i] = nums1[m - 1];
                m--;
                continue;
            }
            if (m <= 0 & n > 0) {
                nums1[i] = nums2[n - 1];
                n--;
                continue;
            }
            if (nums1[m - 1] > nums2[n - 1]) {
                nums1[i] = nums1[m - 1];
                m--;
            } else {
                nums1[i] = nums2[n - 1];
                n--;
            }
        }
    }
}

快慢指针

Linked List Cycle (Medium)

题目描述

给定一个链表，如果有环路，找出环路的开始点。

输入输出样例

　　输入是一个链表，输出是链表的一个节点，如果没有环路，返回一个空指针。
　　链表数据结构:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

c++:

ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    do {
        if (!fast || !fast->next) return nullptr;
        fast = fast -> next -> next;
	slow = slow -> next;
    } while (fast != slow);

    while (fast != next) {
        fast = fast -> next;
        slow = slow -> slow;
    }
    return fast;
}

java:

/**
 * f=2s
 * f=s+nb
 * s=nb
 * f=2nb
 * k=a+nb
 * 简直就是数学题
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode result = null;
//        第一次相遇
        while (true) {
            slow = slow.next;
            fast = fast.next;
            if (fast == null) {
                return null;
            } else {
                fast = fast.next;
            }
            if (fast == null) {
                return null;
            }
            if (slow == fast) {
                break;
            }
        }
        fast = head;
//        第二次相遇
        while (true) {
            if (slow == fast) {
                return slow;
            }
            slow = slow.next;
            fast = fast.next;
        }
    }
}

滑动窗口

Minimum Window Substring (Hard)

题目描述

给定两个字符串S和T,求S中包含T所有字符的最短连续子字符串的长度, 同时要求时间复杂度不得超过O(n)。

输入输出样例

输入是两个字符串S和T,输出是一个S字符串的子串。

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

c++:
```c++
string minWindow(string S, string T) {
    //先统计T中的字符情况
    vector<int> chars(128, 0);
    vector<bool> flags(128, false);
    for (auto i : T) {
        ++chars[i];
        flags[i] = true;
    }
    //先确定S是否包含T,再滑动窗口
    int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;
    for (auto r : S) {
        if (flags[r]) {
            if (--chars[r] > 0)
                ++cnt;
        //s都包含T后，探索最短字符串
            while (cnt == T.size()) {
                if (r - l + 1 < min_size) {
                    min_l = l;
                    min_size = r - l + 1;
                }
                if (flags[S[l]] && ++chars[S[l]] > 0) {
                    --cnt;
                }
                ++l;
            }
        }            
    }
    return min_size < S.size() ? "" : S.substr(min_l, min_size);
}

java:

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> hs = new HashMap<Character, Integer>();
        HashMap<Character, Integer> ht = new HashMap<Character, Integer>();
        String ans = "";
        for (int i = 0; i < t.length(); i++) {
            ht.put(t.charAt(i), ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        Integer cnt = 0;
        Integer max = Integer.MAX_VALUE;
        for (int i = 0, j = 0; j < s.length(); j++) {
            hs.put(s.charAt(j), hs.getOrDefault(s.charAt(j), 0) + 1);
            if (ht.containsKey(s.charAt(j)) && ht.get(s.charAt(j)) >= hs.get(s.charAt(j))) {
                cnt++;
            }
            while (i < j && (!ht.containsKey(s.charAt(i)) || ht.get(s.charAt(i)) < hs.get(s.charAt(i)))) {
                hs.put(s.charAt(i), hs.get(s.charAt(i)) - 1);
                i++;
            }
            if (cnt == t.length()) {
                Integer cur = j - i + 1;
                if (cur < max) {
                    max = cur;
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }
}