Two pointers problems
Key Points:
- Time complexity evaluation: pointers back and forth? Minimum Size Subarray Sum
- One loop or two loop?
- “left<right” or “left<=right”? Strobogrammatic Number
## Blog link: https://code.dennyzhang.com/strobogrammatic-number maps = [('0', '0'), ('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')] left, right = 0, len(num)-1 while left<=right: if (num[left], num[right]) not in maps: return False left, right = left+1, right-1 return True
- Use range to change pointer, instead of manual ways. Minimum Window Substring
## Blog link: https://code.dennyzhang.com/minimum-window-substring left, right = 0, 0 for right in range(0, len1): m1[s[right]] += 1 if self.isTooSmall(m1, m2): continue # find a match, then check whether window too big while m1[s[left]] > m2[s[left]]: m1[s[left]] -= 1 left += 1 # find a candidate if min_len > right-left+1: min_len, res = right-left+1, s[left:right+1] return res
Sliding window:
- Whether left and right are included?
See all twopointer problems: #twopointer
- Review: TwoPointers Problems
- LintCode: Reverse Array
- LintCode: Delete Characters
- LintCode: 3Sum II
- Leetcode: Valid Triangle Number
- Leetcode: Valid Palindrome
- Leetcode: Two Sum IV – Input is a BST
- Leetcode: Two Sum II – Input array is sorted
- Leetcode: Two Sum
- Leetcode: Sum of Square Numbers
- Leetcode: Subarray Product Less Than K
- Leetcode: Squares of a Sorted Array
- Leetcode: Sort Colors
- Leetcode: Sort Array By Parity
- Leetcode: Reverse Only Letters
- Leetcode: Remove Nth Node From End of List
- Leetcode: Minimum Size Subarray Sum
- Leetcode: Longest Substring Without Repeating Characters
- Leetcode: Long Pressed Name
- Leetcode: K-diff Pairs in an Array
- Leetcode: DI String Match
- Leetcode: Count Binary Substrings
- Leetcode: Container With Most Water
- Leetcode: Assign Cookies
- Leetcode: 4Sum
- Leetcode: 3Sum Smaller
- Leetcode: 3Sum Closest
- Leetcode: 3Sum
See more blog_posts.
Share It, If You Like It.