目录
一、二分查找
二、移除元素
三、x的平方根
四、删除链表的倒数第N个节点
五、长度最小的子数组
六、链表相交
七、反转字符串
八、环形链表II
九、三数之和
十、四数之和
一、二分查找
题目地址：力扣
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while left<=right:
middle = (left+right)//2
guess = nums[middle]
if guess == target:
return middle
# break
elif guess > target:
right = middle-1
else:
left = middle+1
return -1二、移除元素
题目地址：力扣
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
length = len(nums)
left = 0
for right in range(length):
if nums[right] != val:
nums[left] = nums[right]
left = left+1
return left三、x的平方根
题目地址：力扣
class Solution:
def mySqrt(self, x : int ) -> int:
if x == 0:
return 0
left = 1
right = x
while left <= right:
mid = (left + right)//2
if mid**2 == x :
return int(mid)
elif mid**2 > x:
right = mid
else:
if (mid + 1) ** 2 > x:
return math.floor(mid)
else:
left = mid四、删除链表的倒数第N个节点
题目地址：力扣
class Solution:
def removeNthFromEnd(self,head:Optional[ListNode],n:int)->Optional[ListNode]:
dummy_head = ListNode(next=head)
fast = dummy_head
slow = dummy_head
for i in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy_head.next五、长度最小的子数组
题目地址：力扣
class Solution:
def minSubArrayLen(self,target:int,nums:List[int])->int:
left = 0
right = 0
length = len(nums)
min_len = length+1
cur_sum = 0
for i in range(length):
# while right < length:
cur_sum = cur_sum + nums[right]
while cur_sum >= target:
min_len = min(right - left + 1 , min_len)
cur_sum -= nums[left]
left = left + 1
right = right + 1
return min_len if min_len != length+1 else 0六、链表相交
class Solution:
def getIntersectionNode(self, headA:ListNode, headB:ListNode) -> ListNode:
curA = headA
curB = headB
while curB != curA:
curA = curA.next if curA else headB
curB = curB.next if curB else headA
return curB七、反转字符串
题目地址：力扣
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left, right = 0, len(s) - 1
# 该方法已经不需要判断奇偶数，经测试后时间空间复杂度比用 for i in range(len(s)//2)更低
# 因为while每次循环需要进行条件判断，而range函数不需要，直接生成数字，因此时间复杂度更低。推荐使用range
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1八、环形链表II
题目地址：力扣
class Solution:
def detectCycle(self,head:ListNode)->ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None九、三数之和
题目地址：力扣文章来源：https://www.toymoban.com/news/detail-509915.html
class Solution:
def threeSum(self, nums:List[int])->List[List[int]]:
length = len(nums)
# right = length - 1
res = []
nums.sort()
for i in range(length - 2):
# 如果第一个元素已经大于0，不需要进一步检查
if nums[i] > 0:
return res
left = i + 1
right = length - 1
# 跳过相同元素以避免重复
if i > 0 and nums[i] == nums[i-1]:
continue
while left < right:
if nums[i] + nums[left] + nums[right] > 0:
right -= 1
elif nums[i] + nums[left] + nums[right] < 0:
left += 1
else:
res.append([nums[i], nums[left], nums[right]])
# 跳过相同的元素以避免重复
while right > left and nums[right] == nums[right - 1]:
right -= 1
while right > left and nums[left] == nums[left + 1]:
left += 1
right -= 1
left += 1
return res十、四数之和
题目地址：力扣文章来源地址https://www.toymoban.com/news/detail-509915.html
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
length = len(nums)
nums.sort()
for i in range(length):
# 剪枝
if nums[i] > target and target > 0:
break
# 去重
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, length):
if j > i+1 and nums[j] == nums[j - 1]:
continue
left = j+1
right = length - 1
while left < right:
if nums[i] + nums[j] + nums[left] + nums[right] > target:
right -= 1
elif nums[i] + nums[j] + nums[left] + nums[right] < target:
left += 1
else:
res.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
right -= 1
left += 1
return res到了这里，关于双指针法的应用场景的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
