力扣 - 剑指 Offer 57 - II. 和为s的连续正数序列
2021/10/30 6:10:45
本文主要是介绍力扣 - 剑指 Offer 57 - II. 和为s的连续正数序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 57 - II. 和为s的连续正数序列
思路1(双指针/滑动窗口)
- 所谓滑动窗口,就是需要我们从一个序列中找到某些连续的子序列,我们可以使用两个for循环来遍历查找,但是未免效率太低了。因此我们可以用一个窗口,从左到右只需要遍历一次,然后每次判断当前窗口是否满足条件,不满足就扩大窗口或者缩小窗口,当滑动窗口从左边滑动到了右边,就可以得到最优解了。
- 滑动窗口的左边界和右边界都只能向右移动,因此只遍历一遍数组,从而时间复杂度是\(O(N)\)
- 该题要求是待遍历的序列是从1~target可构建一个滑动窗口从左向右滑动,窗口边界为
left
、right
,初始的时候left=left=1
- 窗口的有效范围就是窗口左边界要小于右边界,即
left < right
- 每次循环中,将窗口里面的数字的总和
sum
与target
进行比较:- 如果
target > sum
,说明窗口大了,需要将当前left
从sum
中删除,同时left
右移一步 - 如果
target < sum
,说明窗口笑了,需要将当前right
从sum
中删除,同时right
右移一步 - 如果
target = sum
,则找到一段序列等于target
,记录下该子序列,同时left
向右移动一步
- 如果
- 我们以
target=9
为例,求解流程如下:
代码
class Solution { public int[][] findContinuousSequence(int target) { int sum = 3; int left = 1; int right = 2; List<int[]> res = new ArrayList<>(); while (left < right) { // 当前窗口符合要求 if (sum == target) { // 加入到结果集中 int[] temp = new int[right - left + 1]; for (int i = left; i <= right; i++) { temp[i-left] = i; } res.add(temp); } // 窗口过大,要缩小窗口 if (sum >= target) { // 这里要先将left从sum中减去,然后再右移一位,因为当前left是即将被移出窗口,这样才能保证left是窗口的左边界 sum -= left; left++; } else if (sum < target) { // 这里要先将right自增,然后将right加入到sum中,因为先自增才能获取到窗口后一位的元素,然后加入到窗口中,保证了right是窗口的右边界 right++; sum += right; } } return res.toArray(new int[res.size()][]); } }
复杂度分析
- 时间复杂度:\(O(N)\),其中
N=target
- 空间复杂度:\(O(1)\)
这篇关于力扣 - 剑指 Offer 57 - II. 和为s的连续正数序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20登录鉴权入门:打造安全的用户认证系统
- 2024-09-20动态表格入门:新手必读教程
- 2024-09-20动态菜单项入门:轻松掌握基础知识
- 2024-09-20动态面包屑入门:轻松掌握面包屑导航技巧
- 2024-09-20动态权限入门:新手必读指南
- 2024-09-20动态主题处理入门:轻松掌握网站主题切换技巧
- 2024-09-20富文本编辑器入门:新手必读指南
- 2024-09-20功能权限入门:轻松掌握权限管理基础
- 2024-09-20后台管理系统开发入门:新手必读教程
- 2024-09-20后台开发入门:新手必读教程