57 - II. 和为s的连续正数序列【双指针】
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
2. 标签
数组
双指针
滑动窗口
3. 解法 - 双指针
这里也是在滑动窗口嘛,和另一个有些区别,下次再看看。
3.1 Java
class Solution {
public int[][] findContinuousSequence(int target) {
// 最终结果
List<int[]> resList = new ArrayList<int[]>();
// 当前枚举区间为 [start, end]
int start = 1;
int end = 2;
while (start < end) {
// 序列之和,使用求和公式
int sum = (start + end) * (end - start + 1) / 2;
// 如果等于 target,就找到了一个合法序列,加入结果列表
if (sum == target) {
// 当前合法序列
int[] curRes = new int[end - start + 1];
for (int i = start; i <= end; ++i) {
curRes[i - start] = i;
}
// 添加到结果列表中
resList.add(curRes);
// 以 start 为起点的合法序列最多只有一个,所以需要枚举下一个起点,将 start 右移
start++;
} else if (sum < target) {
// 序列之和比目标更小,说明还可以将 end 右移,以获得更大的值
end++;
} else {
// 序列之和比目标更大,说明以 start 为起点不存在一个 end 使得 sum = target
// 此时应该枚举下一个起点,将 start 右移
start++;
}
}
// 循环结束,得到所有的合法序列
return resList.toArray(new int[resList.size()][]);
}
}
3.2 Kotlin
class Solution {
fun findContinuousSequence(target: Int): Array<IntArray> {
// 最终结果
val resList = ArrayList<IntArray>()
// 当前枚举区间为 [start, end]
var start = 1
var end = 2
while (start < end) {
// 序列之和,使用求和公式
val sum = (start + end) * (end - start + 1) / 2
// 如果等于 target,就找到了一个合法序列,加入结果列表
if (sum == target) {
// 当前合法序列
val curRes = IntArray(end - start + 1)
for (i in start..end) {
curRes[i - start] = i
}
// 添加到结果列表中
resList.add(curRes)
// 以 start 为起点的合法序列最多只有一个,所以需要枚举下一个起点,将 start 右移
start++
} else if (sum < target) {
// 序列之和比目标更小,说明还可以将 end 右移,以获得更大的值
end++
} else {
// 序列之和比目标更大,说明以 start 为起点不存在一个 end 使得 sum = target
// 此时应该枚举下一个起点,将 start 右移
start++
}
}
// 循环结束,得到所有的合法序列
return resList.toTypedArray()
}
}
3.3 复杂度分析
时间复杂度
O(target)
:由于题目要求序列长度至少大于 2,所以枚举的上界为 。又由于两个指针一直单调增加,最多移动 次,所以时间复杂度为O(target)
。空间复杂度
O(1)
:只使用到了常数大小的额外空间。
为啥是这个上界 - - 先搁着
4. 解法 - 滑动窗口 #TODO
4.1 Java
4.2 Kotlin
4.3 复杂度分析
时间复杂度
O()
:空间复杂度
O()
:
5. 参考
最后更新于
这有帮助吗?