Two Pointer Flashcards
- Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
Example 4:
Input: s = “”
Output: 0
Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
用two pointer 去走，fast 會先往下走直到遇見重複的，用hashmap記錄遇過的letter，一旦遇到map裡面有的且map裡的index >=slow，就讓slow直接等於 i+1
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
fast, slow = 0, 0
n = len(s)
table = {}
res = 0
while fast < n:
if s[fast] in table and table[s[fast]] >= slow:
slow = table[s[fast]] + 1
table[s[fast]] = fast
res = max(res, fast - slow + 1)
fast += 1
return res
- Container With Most Water
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Example 3:
Input: height = [4,3,2,1,4]
Output: 16
Example 4:
Input: height = [1,2,1]
Output: 2
Constraints:
2 <= height.length <= 3 * 104
0 <= height[i] <= 3 * 104
two pointer從左右夾擊，這個概念就是讓width從最大開始，固定width只會越來越小之後，就只要考慮height是否有比現在的大，並且每次只有小的那一邊靠近中間
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l, r = 0, len(height) - 1
res = 0
prev_l, prev_r = -1, -1
while l < r:
if height[l] > prev_l or height[r] > prev_r:
amount = min(height[l], height[r]) * (r - l)
res = max(res, amount)
prev_l, prev_r = height[l], height[r]
if height[l] < height[r]: l += 1
else: r -= 1
return res
- 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
~~~
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
~~~
無法用n次two sum來做，因為two sum只能處理沒有重複解答的問題。這題要用two pointer解決
先sort 這個list，for loop I，然後用l, r從左右夾擊。
一旦找到一對，l+=1, r-=1 ，並且要用while 把重複的都跳過，不然會有重複答案。
如果不是一對
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1- 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [], target = 0
Output: []
Constraints:
0 <= nums.length <= 200
- 109 <= nums[i] <= 109
- 109 <= target <= 109
做ksum 遞迴k-2次 for loop然後做two sum
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if len(nums) < 4: return []
nums.sort()
return self.ksum(nums, target, 4)
# -2,-1,0,0,1,2
def ksum(self, nums, target, k):
if len(nums) == 0 or nums[0] * k > target or target > nums[-1] * k:
return []
if k == 2:
return self.twosum(nums, target)
out = []
for i in xrange(len(nums) - (k - 1)):
if i > 0 and nums[i] == nums[i-1]: continue
tmp = target - nums[i]
res = self.ksum(nums[i+1:], tmp, k - 1)
for r in res:
out.append([nums[i]] + r)
return out
def twosum(self, nums, target):
memo = {}
out = []
for i in xrange(len(nums)):
if len(out) == 0 or out[-1][1] != nums[i]:
if target - nums[i] in memo:
out.append([target - nums[i], nums[i]])
memo[nums[i]] = i
return out
