NeetCode 150 全問の解き方とポイントまとめ Two Pointers
Two Pointers
本記事は以下記事の一部です。
NeetCode 150 全問の解き方とポイントまとめ & 感想
Arrays & Hashing と一緒で Two Pointers も比較的とっつきやすい印象です。ただこの辺の分野は概念が簡単な分工夫しやすいのか問題パターンが多岐に渡るそうなのでその点は注意。
10. Valid Palindrome
Link | |
Difficulty (Easy, Medium, Hard) | Easy |
Time Complexity | O(N) |
Space Complexity | O(N) |
The personal need for review (1 ~ 10) | 2 |
Memo |
|
Problem
Given a string s, return true if it is a palindrome, otherwise return false.
A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
Example 1:
Input: s = "Was it a car or a cat I saw?"
Output: true
Explanation: After considering only alphanumerical characters we have "wasitacaroracatisaw", which is a palindrome.
Example 2:
Input: s = "tab a cat"
Output: false
Explanation: "tabacat" is not a palindrome.
Constraints:
1 <= s.length <= 1000
s is made up of only printable ASCII characters.
Solution
import re
class Solution:
def removeNonAlphanumeric(self, text: str) -> str:
# 正規表現で non-alphanumeric 文字を削除
return re.sub(r'[^a-zA-Z0-9]', '', text)
def isPalindrome(self, s: str) -> bool:
# lowerケースのアルファベットと数字だけにする(空白も取り除く)
removed_nonalpha = self.removeNonAlphanumeric(s)
low_alpha = ''.join(removed_nonalpha.split()).lower()
l, r = 0, len(low_alpha) - 1
while l < r:
if low_alpha[l] != low_alpha[r]:
return False
l += 1
r -= 1
return True
11. Two Sum II Input Array Is Sorted
Link | |
Related Problem | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O(N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 2 |
Memo |
|
Problem
Given an array of integers numbers that is sorted in non-decreasing order.
Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.
There will always be exactly one valid solution.
Your solution must use O(1)
O(1) additional space.
Example 1:
Input: numbers = [1,2,3,4], target = 3
Output: [1,2]
Explanation:
The sum of 1 and 2 is 3. Since we are assuming a 1-indexed array, index1 = 1, index2 = 2. We return [1, 2].
Solution
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers)-1
while l < r:
total = numbers[l] + numbers[r]
if total == target:
return [l+1, r+1]
elif total < target:
l += 1
else:
r -= 1
12. 3Sum
Link | |
Related Problem | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O(N^2) |
Space Complexity | O(N) |
The personal need for review (1 ~ 10) | 5 |
Memo |
|
Problem
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.
The output should not contain any duplicate triplets. You may return the output and the triplets in any order.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 1000
-10^5 <= nums[i] <= 10^5
Solution
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums)-2):
# nums[i]が前回と同じ値になると結果が重複するので
# そうならないところまでiのポインターを進める
if i > 0 and nums[i-1] == nums[i]:
continue
l, r = i+1, len(nums)-1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total == 0:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
elif total < 0:
l += 1
else:
r -= 1
return res
13. Container With Most Water
Link | |
Related Problem | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O(N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 5 |
Memo |
|
Problem
You are given an integer array heights where heights[i] represents the height of the ith bar.
You may choose any two bars to form a container. Return the maximum amount of water a container can store.
Example 1:
Input: height = [1,7,2,5,4,7,3,6]
Output: 36
Example 2:
Input: height = [2,2,2]
Output: 4
Constraints:
2 <= height.length <= 1000
0 <= height[i] <= 1000
Solution
class Solution:
def maxArea(self, heights: List[int]) -> int:
l, r = 0, len(heights) - 1
max_area = 0
while l < r:
width = r - l
height = 0
if heights[l] <= heights[r]:
# 高さが低い方を内側に動かす
# 同じ高さだった場合はどちらを動かしても結果は変わらない。
# 仮に動かした方の次のバーが高くても、動かしてない方のバーの高さで
# 面積は決まるので、動かす前より面積が大きくなることはない
height = heights[l]
l += 1
else:
height = heights[r]
r -= 1
area = height * width
max_area = max(max_area, area)
return max_area
14. Trapping Rain Water
Link | |
Related Problem | |
Difficulty (Easy, Medium, Hard) | Hard |
Time Complexity | O(N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 6 |
Memo |
|
Problem
You are given an array non-negative integers heights which represent an elevation map. Each value heights[i] represents the height of a bar, which has a width of 1.
Return the maximum area of water that can be trapped between the bars.
Example 1:
Input: height = [0,2,0,3,1,0,1,3,2,1]
Output: 9
Solution
class Solution:
def trap(self, height: List[int]) -> int:
l, r = 0, len(height)-1
left_max = height[l]
right_max = height[r]
water = 0
while l < r:
if height[l] <= height[r]:
l += 1
if height[l] < left_max:
water += left_max - height[l]
else:
left_max = height[l]
else:
r -= 1
if height[r] < right_max:
water += right_max - height[r]
else:
right_max = height[r]
return water