关于使用双指针的相关题目-python双指针1.JZ 57 和为s的两个数2. JZ22 链表中的倒数第k个节点3 JZ57 和为s的连续正数序列

101 阅读 0 评论 67 点赞

我是靠谱客的博主儒雅奇异果，这篇文章主要介绍关于使用双指针的相关题目-python双指针1.JZ 57 和为s的两个数2. JZ22 链表中的倒数第k个节点3 JZ57 和为s的连续正数序列，现在分享给大家，希望可以做个参考。

双指针

文章目录

双指针
1.JZ 57 和为s的两个数
- 代码
2. JZ22 链表中的倒数第k个节点
- 代码
3 JZ57 和为s的连续正数序列
- 代码

1.JZ 57 和为s的两个数

JZ57

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #注意充分利用好递增排序的条件
        mins, maxs = 0, len(nums)-1
        while mins < maxs:
            sum = nums[mins] + nums[maxs]
            if sum < target:
                mins += 1
            if sum > target:
                maxs -= 1
            if sum == target:
                return [nums[mins], nums[maxs]]
        return [] #如果不存在，则返回空数组

该题与lc1 两数之和有点点类似，而两数之和并不是递增的数组，所以lc1 可以采用哈希数组来存储
lc1 两数之和代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

2. JZ22 链表中的倒数第k个节点

JZ22 链表中的倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast, slow = head, head
        while fast and k > 0: #fast指针先移动k步
            fast = fast.next
            k -= 1
        while fast:
            fast = fast.next
            slow = slow.next
        return slow  #当fast移动到尾端时，此时在第k个node上

3 JZ57 和为s的连续正数序列

JZ57 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

代码

暴力的解法（不推荐）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        end = target//2 + 2 #最大的两个连续数肯定不会超过target/2+1，这里加2 是为了下面的循环
        #//为整除，返回整数（向下），/为浮点数除法，返回浮点数
        res = [] #存储最终的结果
        for i in range(1,end-1):          
            s = i
            for j in range(i+1, end): #因为题目要求至少两个数，所以这里从i+1开始
                s += j             
                if s == target:
                    temp = list(range(i, j+1))
                    res.append(temp) #如果符合，则将temp的结果加入res中，并break结束本轮的循环
                    break
                if s > target:
                    break #如果大了，直接结束本轮的循环
        return res

在这里插入图片描述

双指针法（滑动窗口）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:      
        i = 1 # 滑动窗口的左边界
        j = 1  # 滑动窗口的右边界
        sum = 0 # 滑动窗口中数字的和
        res = [] #最终结果

        while i <= target // 2:
            if sum < target:# 右边界向右移动
                sum += j
                j += 1
            elif sum > target:
                sum -= i # 左边界向右移动
                i += 1
            else:
                temp = list(range(i, j))
                res.append(temp)
                sum -= i # 左边界向右移动
                i += 1
        return res

在这里插入图片描述
可以对比双指针的解法比暴力解法效率几乎快了4倍！

或者

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        l, sum = 1, 0
        res = []
        for r in range(1, target // 2 + 2):
            sum += r 
            while sum >= target: #只有在大于或等于的时候才进入循环
                if sum == target:
                    res.append(list(range(l, r + 1)))
                sum -= l #直接减去左边界，然后左边界往右移
                l += 1
        return res