1. 题目介绍（57. 和为 s 的数字）

面试题57：和为 s 的数字， 一共分为两小题：

• 题目一：和为 s 的两个数字
• 题目二：和为 s 的连续正数序列

2. 题目1：和为s的两个数字

题目链接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/submissions/

2.1 题目介绍

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

【测试用例】：
示例 1：

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

示例2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

【条件约束】：

限制：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

2.2 题解 – 首尾指针 – O(n)

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

【解题思路】：

1. 暴力枚举：先在数组中固定一个数组，再依次判断数组中其余 n-1 个数字与它的和是不是等于 s；
2. 首尾指针：根据 两端逼近 的原则：
   • 我们首先定义两个指针，第一个指针指向数组的 第一个（最小的）数字，第二个指针指向数组的 最后一个（最大的）数字。
   • 如果 当前的两数和 小于输入目标值，那么就将首指针的索引位置向后移动一个单位；
   • 反之，如果 当前的两数和 大于输入目标值，那么就将尾指针的索引位置向前移动一个单位，直至找到符合条件的两个数字，或者首指针索引位置超过了尾指针的索引位置时结束。

class Solution {// Solution1：双指针// Core：通过首尾指针来不断移动改变两数和，直至等于targetpublic int[] twoSum(int[] nums, int target) {// 无效输入判断if (nums.length <= 0) return null;// 定义首尾指针int start = 0, end = nums.length-1;// 开始循环遍历数组// 如果还在正确的边界范围中，则进行循环while (start < end) {// 获取当前两数和int curData = nums[start] + nums[end];//  当前两数和 等于 目标值，则返回 if (curData == target) return new int[]{nums[start],nums[end]};// 如果 大于 目标值，则让较大数字位置向前移动一位else if (curData > target) end--;// 如果 小于，则让较小数字位置向后移动一位else start++;}// 循环结束，该数组中不存在两数和等于target，返回nullreturn null;}
}

3. 题目2：和为 s 的连续正数序列

题目链接：https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

3.1 题目介绍

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

【测试用例】：
示例1：

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

示例2：

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

【条件约束】：

限制：

• 1 <= target <= 10^5

3.2 题解 – 滑动窗口 – O(n)

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

【解题思路】：
滑动窗口 的重要性质是：窗口的左边界和右边界 永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n).

• 当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
• 当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
• 由于题目中要求序列至少要有两个数字，所以我们需要一直增加 left 左边界到 （1+target）/2 为止。

class Solution {// Solution1：滑动窗口public int[][] findContinuousSequence(int target) {int left = 1;  // 滑动窗口的左边界int right = 2;  // 滑动窗口的右边界int mid = (1 + target)/2;  // 保证序列最少有两个数int sum = left + right;  // 滑动窗口中数字的和List<int[]> res = new ArrayList<>();while (left < mid) {if (sum < target) {// 右边界向右移动right++;sum += right;} else if (sum > target) {// 左边界向右移动sum -= left;left++;} else {// 记录结果int[] arr = new int[right-left+1];for (int k = left; k <= right; k++) {arr[k-left] = k;}res.add(arr);// 左边界向右移动sum -= left;left++;}}return res.toArray(new int[res.size()][]);}
}

4. 参考资料

[1] 什么是滑动窗口，以及如何用滑动窗口解这道题（C++/Java/Python）