雙指標

# python
# LC 26 - Remove Duplicates from Sorted Array
# IDEA: fast reads every index; slow is the last kept slot, advanced only for a new value
# time = O(n), space = O(1)
def removeDuplicates(nums):
    if not nums:
        return 0
    slow = 0                          # nums[0..slow] = the unique values seen so far
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:  # a value not kept yet
            slow += 1                 # open the next write slot
            nums[slow] = nums[fast]   # copy it forward
        # equal: a duplicate, fast moves on and slow stays
    return slow + 1                   # slow is an index; the count is index + 1

// java
// LC 26 - Remove Duplicates from Sorted Array
// IDEA: fast reads every index; slow is the last kept slot, advanced only for a new value
// time = O(n), space = O(1)
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int slow = 0;                        // nums[0..slow] = the unique values seen so far
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;                      // open the next write slot
            nums[slow] = nums[fast];     // overwrite with the new unique value
        }
    }
    return slow + 1;
}

nums = [0,0,1,1,2]
fast=1  0 == nums[0]   skip                  slow=0
fast=2  1 != 0         slow=1, nums[1]=1     [0,1,1,1,2]
fast=3  1 == nums[1]   skip                  slow=1
fast=4  2 != 1         slow=2, nums[2]=2     [0,1,2,1,2]
return 3 -> nums[:3] = [0,1,2]

# python
# LC 27 - Remove Element
# IDEA: copy every element that is not val down to the write slot
# time = O(n), space = O(1)
def removeElement(nums, val):
    slow = 0                          # next free write slot
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

// java
// LC 27 - Remove Element
// IDEA: copy every element that is not val down to the write slot
// time = O(n), space = O(1)
public int removeElement(int[] nums, int val) {
    int slow = 0;                        // next free write slot
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

# python
# LC 11 - Container With Most Water
# IDEA: measure the widest pair, then drop the shorter wall: it cannot do better with a narrower partner
# time = O(n), space = O(1)
def maxArea(height):
    left = 0
    right = len(height) - 1
    best = 0
    while left < right:
        width = right - left
        best = max(best, min(height[left], height[right]) * width)
        if height[left] < height[right]:   # left is the bottleneck: discard it
            left += 1
        else:                              # right is (or ties): discard it
            right -= 1
    return best

// java
// LC 11 - Container With Most Water
// IDEA: measure the widest pair, then drop the shorter wall: it cannot do better with a narrower partner
// time = O(n), space = O(1)
public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int best = 0;
    while (left < right) {
        int width = right - left;
        best = Math.max(best, Math.min(height[left], height[right]) * width);
        if (height[left] < height[right]) {
            left++;                       // left is the bottleneck: discard it
        } else {
            right--;
        }
    }
    return best;
}

// java
// LC 27 Remove Element - Bidirectional variant
// IDEA: a val at l is overwritten by the rightmost element; l only advances past a kept element
// time = O(n), space = O(1)
/**
 * Key Idea:
 *   - l starts at 0, r starts at nums.length - 1
 *   - If nums[l] == val, OVERWRITE it with nums[r] and shrink r
 *     (do NOT advance l yet — the new nums[l] might also be val)
 *   - If nums[l] != val, it is a "good" element → advance l
 *   - When l > r, l equals the count of valid elements
 *
 * //--------------------
 * Example 1
 * //--------------------
 * nums = [3,2,2,3], val = 3
 *
 * [3,2,2,3]   nums[l]=3==val, nums[l]=nums[r]=3, r--
 *  l     r
 *
 * [3,2,2,3]   nums[l]=3==val, nums[l]=nums[r]=2, r--
 *  l   r
 *
 * [2,2,2,3]   nums[l]=2!=val, l++
 *  l r
 *
 * [2,2,2,3]   nums[l]=2!=val, l++
 *    lr
 *
 * l(2) > r(1), return l = 2
 *
 * //--------------------
 * Example 2
 * //--------------------
 * nums = [0,1,2,2,3,0,4,2], val = 2
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=0!=val, l++
 *  l               r
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=1!=val, l++
 *    l             r
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=2==val, nums[l]=nums[r]=2, r--
 *      l           r
 *
 * [0,1,2,2,3,0,4,2]   nums[l]=2==val, nums[l]=nums[r]=4, r--
 *      l         r
 *
 * [0,1,4,2,3,0,4,2]   nums[l]=4!=val, l++
 *      l       r
 *
 * [0,1,4,2,3,0,4,2]   nums[l]=2==val, nums[l]=nums[r]=0, r--
 *        l     r
 *
 * [0,1,4,0,3,0,4,2]   nums[l]=0!=val, l++
 *        l   r
 *
 * [0,1,4,0,3,0,4,2]   nums[l]=3!=val, l++
 *          l r
 *
 * l(5) > r(4), return l = 5
 */
public int removeElement(int[] nums, int val) {
    int l = 0;
    int r = nums.length - 1;

    while (l <= r) {
        if (nums[l] == val) {
            // Overwrite with rightmost element, shrink right boundary
            // do NOT advance l — the new nums[l] might also be val
            nums[l] = nums[r];
            r--;
        } else {
            // Good element confirmed, advance left
            l++;
        }
    }

    // l is exactly the count of non-val elements
    return l;
}

// java
// IDEA: swap the two ends, move both inward until they meet
// time = O(n), space = O(1)
void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}

# python
# LC 5 - Longest Palindromic Substring
# IDEA: try all 2n - 1 centres (each char, each gap); expand while the ends match; keep the widest
# time = O(n^2), space = O(1)
def longestPalindrome(s):
    def expand(left, right):
        # grow while s[left..right] is a palindrome
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # the loop stopped one step too far on each side
        return left + 1, right          # half-open [start, end)

    best_start, best_end = 0, 0
    for center in range(len(s)):
        for left, right in ((center, center), (center, center + 1)):   # odd, then even
            start, end = expand(left, right)
            if end - start > best_end - best_start:
                best_start, best_end = start, end
    return s[best_start:best_end]

// java
// LC 5 - Longest Palindromic Substring
// IDEA: try all 2n - 1 centres (each char, each gap); expand while the ends match; keep the widest
// time = O(n^2), space = O(1)
public String longestPalindrome(String s) {
    int bestStart = 0;
    int bestEnd = 0;                                 // half-open [bestStart, bestEnd)
    for (int center = 0; center < s.length(); center++) {
        int[] odd = expand(s, center, center);
        int[] even = expand(s, center, center + 1);
        if (odd[1] - odd[0] > bestEnd - bestStart) {
            bestStart = odd[0];
            bestEnd = odd[1];
        }
        if (even[1] - even[0] > bestEnd - bestStart) {
            bestStart = even[0];
            bestEnd = even[1];
        }
    }
    return s.substring(bestStart, bestEnd);
}

private int[] expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return new int[]{left + 1, right};               // undo the last failed step
}

s = "cbbd"
center 0  odd  "c"          even c|b  stop      best "c"
center 1  odd  "b"          even b|b  -> "bb", then c|d stop   best "bb"
center 2  odd  "b"          even b|d  stop
center 3  odd  "d"
return "bb"

# python
# LC 392 - Is Subsequence
# IDEA: j scans t every step; i advances only when s[i] matches (greedy earliest match)
# time = O(|t|), space = O(1)
def isSubsequence(s, t):
    i = 0                                   # next character of s to place
    for j in range(len(t)):                 # t's pointer always moves
        if i < len(s) and s[i] == t[j]:
            i += 1                          # matched: move s's pointer too
    return i == len(s)

// java
// LC 392 - Is Subsequence
// IDEA: j scans t every step; i advances only when s[i] matches (greedy earliest match)
// time = O(|t|), space = O(1)
public boolean isSubsequence(String s, String t) {
    int i = 0;                                      // next character of s to place
    for (int j = 0; j < t.length(); j++) {          // t's pointer always moves
        if (i < s.length() && s.charAt(i) == t.charAt(j)) {
            i++;
        }
    }
    return i == s.length();
}

s = "abc", t = "ahbgdc"
j=0 'a' == s[0]  i=1
j=1 'h'          i=1
j=2 'b' == s[1]  i=2
j=3 'g'  j=4 'd' i=2
j=5 'c' == s[2]  i=3 == len(s) -> true

# python
# LC 88 - Merge Sorted Array
# IDEA: two read pointers at the ends of the valid parts, one write pointer at the very end;
#       always write the larger tail. Loop on p2 only: leftover nums1 is already in place.
# time = O(m + n), space = O(1)
def merge(nums1, m, nums2, n):
    p1 = m - 1              # read nums1 from the end of its valid part
    p2 = n - 1              # read nums2 from its end
    write = m + n - 1       # write from the very end of nums1
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[write] = nums1[p1]
            p1 -= 1
        else:               # nums2's tail is larger or equal, or nums1 is used up
            nums1[write] = nums2[p2]
            p2 -= 1
        write -= 1

// java
// LC 88 - Merge Sorted Array
// IDEA: write the larger tail into the last free slot; loop until nums2 is used up
// time = O(m + n), space = O(1)
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;           // read nums1
    int p2 = n - 1;           // read nums2
    int write = m + n - 1;    // write slot
    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[write] = nums1[p1];
            p1--;
        } else {
            nums1[write] = nums2[p2];
            p2--;
        }
        write--;
    }
}

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

| Step | p1 | p2 | write | Compare                 | Action  | nums1          |
|------|----|----|-------|-------------------------|---------|----------------|
| init |  2 |  2 |   5   | —                       | setup   | [1,2,3,0,0,0]  |
|  1   |  2 |  2 |   5   | nums1[2]=3 < nums2[2]=6 | write 6 | [1,2,3,0,0,6]  |
|  2   |  2 |  1 |   4   | nums1[2]=3 < nums2[1]=5 | write 5 | [1,2,3,0,5,6]  |
|  3   |  2 |  0 |   3   | nums1[2]=3 > nums2[0]=2 | write 3 | [1,2,3,3,5,6]  |
|  4   |  1 |  0 |   2   | nums1[1]=2 == nums2[0]=2| write 2 | [1,2,2,3,5,6]  |
|  5   |  1 | -1 |   1   | p2 < 0                  | STOP    | [1,2,2,3,5,6]  |

nums1[0..1] = [1,2] is already in place -> no flush step

# python
# LC 75 - Sort Colors
# IDEA: 0 -> swap into the low region, 2 -> swap into the high region, 1 -> leave in place
# time = O(n), space = O(1)
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:                  # nums[mid..high] is still unseen
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1                    # what came from low is a 1 (or mid itself): already seen
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                   # do NOT move mid: the value from high is unseen

// java
// LC 75 - Sort Colors
// IDEA: 0 -> swap into the low region, 2 -> swap into the high region, 1 -> leave in place
// time = O(n), space = O(1)
public void sortColors(int[] nums) {
    int low = 0;                  // next slot for a 0
    int mid = 0;                  // current element
    int high = nums.length - 1;   // next slot for a 2
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums, low, mid);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums, mid, high);
            high--;               // the swapped-in value is unseen: check it next round
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

nums = [2,0,2,1,1,0]          low mid high
mid=0 is 2 -> swap with high   [0,0,2,1,1,2]   0  0  4
mid=0 is 0 -> swap with low    [0,0,2,1,1,2]   1  1  4
mid=1 is 0 -> swap with low    [0,0,2,1,1,2]   2  2  4
mid=2 is 2 -> swap with high   [0,0,1,1,2,2]   2  2  3
mid=2 is 1                                     2  3  3
mid=3 is 1                                     2  4  3   mid > high: done

# python
# LC 141 - Linked List Cycle; LC 142 - Linked List Cycle II (the entry node)
# IDEA: slow 1 step, fast 2 steps -> they meet iff there is a cycle; then head and meet point
#       walk 1 step each and meet at the entry
# time = O(n), space = O(1)
def hasCycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:          # identity, not value
            return True
    return False

def detectCycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:          # inside the cycle: now find where it starts
            entry = head
            while entry is not slow:
                entry = entry.next
                slow = slow.next
            return entry
    return None                   # fast fell off the end: no cycle

// java
// LC 141 - Linked List Cycle; LC 142 - Linked List Cycle II (the entry node)
// IDEA: slow 1 step, fast 2 steps -> they meet iff there is a cycle; then head and meet point
//       walk 1 step each and meet at the entry
// time = O(n), space = O(1)
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode entry = head;
            while (entry != slow) {
                entry = entry.next;
                slow = slow.next;
            }
            return entry;
        }
    }
    return null;                  // no cycle: the guard above is what prevents an NPE
}

# python
# LC 567 - Permutation in String
# IDEA: grow right; shrink left until the window is len(s1) long; equal counts = a permutation
# time = O(26 * n), space = O(26)
def checkInclusion(s1, s2):
    need = [0] * 26
    for ch in s1:
        need[ord(ch) - ord('a')] += 1
    window = [0] * 26
    left = 0
    for right in range(len(s2)):
        window[ord(s2[right]) - ord('a')] += 1          # grow
        while right - left + 1 > len(s1):               # too long -> shrink
            window[ord(s2[left]) - ord('a')] -= 1
            left += 1
        if window == need:
            return True
    return False

// java
// LC 567 - Permutation in String
// IDEA: grow right; shrink left until the window is len(s1) long; equal counts = a permutation
// time = O(26 * n), space = O(26)
public boolean checkInclusion(String s1, String s2) {
    int[] need = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        need[s1.charAt(i) - 'a']++;
    }
    int[] window = new int[26];
    int left = 0;
    for (int right = 0; right < s2.length(); right++) {
        window[s2.charAt(right) - 'a']++;               // grow
        while (right - left + 1 > s1.length()) {        // too long -> shrink
            window[s2.charAt(left) - 'a']--;
            left++;
        }
        if (Arrays.equals(window, need)) {
            return true;
        }
    }
    return false;
}

# python
# LC 165 - Compare Version Numbers
# IDEA: i walks version1, j walks version2; each round parses one revision from each side
#       (an exhausted side yields 0) and the first unequal pair decides
# time = O(n1 + n2), space = O(1)
def compareVersion(version1, version2):
    i, j = 0, 0
    n1, n2 = len(version1), len(version2)
    while i < n1 or j < n2:                    # OR: the shorter side keeps yielding 0
        a = 0
        while i < n1 and version1[i] != ".":
            a = a * 10 + int(version1[i])      # leading zeros vanish here
            i += 1
        b = 0
        while j < n2 and version2[j] != ".":
            b = b * 10 + int(version2[j])
            j += 1
        if a != b:
            return -1 if a < b else 1
        i += 1                                 # step over the '.' (harmless past the end)
        j += 1
    return 0

// java
// LC 165 - Compare Version Numbers
// IDEA: i walks version1, j walks version2; each round parses one revision from each side
//       (an exhausted side yields 0) and the first unequal pair decides
// time = O(n1 + n2), space = O(1)
public int compareVersion(String version1, String version2) {
    int i = 0, j = 0;
    int n1 = version1.length(), n2 = version2.length();
    while (i < n1 || j < n2) {
        int a = 0;
        while (i < n1 && version1.charAt(i) != '.') {
            a = a * 10 + (version1.charAt(i) - '0');
            i++;
        }
        int b = 0;
        while (j < n2 && version2.charAt(j) != '.') {
            b = b * 10 + (version2.charAt(j) - '0');
            j++;
        }
        if (a != b) {
            return Integer.compare(a, b);
        }
        i++;
        j++;
    }
    return 0;
}

round  a (from version1)   b (from version2)   result
1      1                   1                   equal, continue
2      "01"  -> 1          "001" -> 1          equal, continue
3      exhausted -> 0      1                   0 < 1 -> return -1