剑指offer 面试题57. 和为s的两个数字（易）

对撞指针和滑动窗口的应用

Question

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

示例 1： 

1
2
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2： 
1
2
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
限制：\(1 <= nums.length <= 10^5\)，\(1 <= nums[i] <= 10^6\)。

测试用例

功能测试（数组中存在和为s的两个数；数组中不存在和为s的两个数）。 特殊输入测试（表示数组的指针为nullptr指针）。

本题考点

考查应聘者思考复杂问题的思维能力。应聘者如果能够通过一两个具体的例子找到规律，那么解决这个问题就容易多了。 考查应聘者的知识迁移能力。应聘者面对第二个问题的时候，能不能把解决第一个问题的思路应用到新的题目上，是面试官考查知识迁移能力的重要指标。

Intuition

对撞指针（双指针的一种特殊形式）

  • 考虑用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1，big 初始化为 len(nums)-1。
    • 如果从 small + big > s，则应该减小两个数的和，也就是减小 big 的值。
    • 如果从 small + big < s，则应该增加两个数的和，也就是增加 small 的值。
  • 如果 small >= big，说明没有找到 smll + big = s，返回 []。
Snipaste_2020-05-16_11-07-57

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        small = 0
        big = len(nums)-1
        while small < big:
            if nums[small] + nums[big] == target:
                return [nums[small], nums[big]]
            elif nums[small] + nums[big] > target:
                big -= 1
            else:
                small += 1
        return []

Extension

Question

面试题 57 - II. 和为 s 的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

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

示例 2：

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

限制：\(1 <= target <= 10^5\)

测试用例

功能测试（存在和为s的连续序列，如9、100等；不存在和为s的连续序列，如4、0等）。 边界值测试（连续序列的最小和3）。

Intuition

滑动窗口

  • 考虑用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1，big 初始化为 2。
    • 如果从 small 到 big 的序列和大于 s，则可以从序列中去掉较小的值，也就是增大small的值。
    • 如果从 small 到 big 的序列和小于 s，则可以增大big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加 small 到(1+s)/2为止。
  • 如果 small >= big，说明没有从 small 到 big 的序列和等于 s，返回 []。

以求和为9的所有连续序列为例，可以用表总结整个过程。

Snipaste_2020-05-16_10-56-13

Code

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]]:
        if target < 1:
            return []
        left = 1  # 滑动窗口的左边界
        right = 1  # 滑动窗口的右边界
        res = []
        while left < target:
            _list = list(range(left, right+1))
            _sum = sum(_list)
            if _sum == target:
                res.append(_list[:])
                # 左边界向右移动
                left += 1
            elif _sum < target:
                 # 右边界向右移动
                right += 1
            else:
                # 左边界向右移动
                left += 1
        return res

Optimization

以上代码还可以做进一步提升，通常我们可以用循环求一个连续序列的和，但考虑到每次操作之后的序列和操作之前的序列相比大部分数字都是一样的，只是增加或者减少了一个数字，因此我们可以在前一个序列的和的基础上求操作之后的序列的和。这样可以减少很多不必要的运算，从而提高代码的效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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:
                # 记录结果
                arr = list(range(i, j))
                res.append(arr)
                # 左边界向右移动
                sum -= i
                i += 1

        return res