剑指Offer-双指针专题

57.1 和为S的两个数字

题目描述

在有序数组中找出两个数，使得和为给定的数S。如果有多对数字的和等于S，输出两个数的乘积最小的。


Input:
[1, 2, 4, 7, 11, 15], 15

Output:
[4, 11]

题解

思路（双指针法）：
使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

时间复杂度O(n)，空间复杂度O(1)

双指针法

class Solution:
    def find_numbers_with_sum(self, nums, target):
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                return [nums[i], nums[j]]
            elif nums[i] + nums[j] < target:
                i += 1
            else:
                j -= 1
        
        return []
    

if __name__ == "__main__":
    nums = [1, 2, 4, 7, 11, 15]
    target = 15
    print(Solution().find_numbers_with_sum(nums, target))

[4, 11]

57.2 和为S的连续正数序列

题目描述

输出所有和为S的连续整数序列，数据范围为0到100。

Input:
9

Output:
[[2, 3, 4], [4, 5]]

题解

思路（滑动窗口）：
区间从[1, 2]开始，两个指针分别指向区间首和尾，使用公式计算区间内子元素之和，如果等于目标数，则记录下该区间的所有数字，同时左区间指针向右，若区间内的序列和小于目标数，则右区间扩展。若区间内的序列和大于目标数，则左区间向右。

时间复杂度O(n)，空间复杂度O(sqrt(n))

滑动窗口

class Solution:
    def find_continuous_sequence(self, target_sum):
        l = 1
        r = 2
        res = []
        while l < r:
            total = (l + r) * (r - l + 1) / 2
            if total == target_sum:
                res.append([i for i in range(l, r+1)])
                l += 1
            elif total < target_sum:
                r += 1
            else:
                l += 1
        
        return res
    

if __name__ == "__main__":
    print(Solution().find_continuous_sequence(9))

[[2, 3, 4], [4, 5]]

58.1 翻转单词序列

题目描述

给定一个句子，翻转单词的顺序，然后输出。

Input:
"This is a sample"

Output:
"sample a is This"

题解

思路：
先翻转整个句子，再翻转每个单词

时间复杂度O(n)，空间复杂度O(1)

翻转单词序列

class Solution:
    def reverse_sentence(self, strs):
        strs = strs[::-1]
        s = strs.split(" ")
        return " ".join(s[i][::-1] for i in range(len(s)))
    

if __name__ == "__main__":
    strs = "This is a sample"
    print(Solution().reverse_sentence(strs))

sample a is This

左旋转字符串

题目描述

将字符串S从第K位置分隔成两个子字符串，并交换这两个子字符串的位置


Input:
S = "abcXYZdef"
K = 3

Output:
"XYZdefabc"

题解

思路1（三次翻转）：
先整个字符串翻转，然后将按K分割字符串，len(字符串)-k左侧的子字符串翻转，再将len(字符串)-k右侧子字符串翻转

时间复杂度O(n)，空间复杂度O(1)

class Solution:
    def left_rotate_string(self, strs, k):
        n = len(strs)
        if n == 0:
            return ""
        if n < k:
            k = k % n
        strs = strs[::-1]
        
        return strs[:n-k][::-1] + strs[n-k:][::-1]
    

if __name__ == "__main__":
    strs = "abcXYZdef"
    k = 3
    print(Solution().left_rotate_string(strs, k))

XYZdefabc

思路2（拼接）：

将字符串后面再加一个字符串，然后取K到K+len(字符串)部分即可，注意保证K要小于len(字符串)。

时间复杂度O(n)，空间复杂度O(1)

class Solution:
    def left_rotate_string(self, strs, k):
        n = len(strs)
        if n == 0:
            return ""
        if n < k:
            k = k % n
        strs = strs * 2
        return strs[k:n+k]
    

if __name__ == "__main__":
    strs = "abcXYZdef"
    k = 3
    print(Solution().left_rotate_string(strs, k))

XYZdefabc

参考文章

本文是笔者通过下列网站学习的记录，有部分修改和补充，转载请注明出处，并附带下面链接。