力扣第180题文件组合,来看看滑动窗口的巧妙思想!
题目链接 https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/解题思路分析该问题要求找出所有连续正整数序列的和等于给定目标值target的序列。采用滑动窗口双指针方法可以高效解决通过动态调整窗口的左右边界来寻找符合条件的序列。关键步骤初始化变量定义三个变量左边界i初始为1、右边界j初始为2、当前窗口和s初始为3。使用ArrayList存储符合条件的序列。滑动窗口调整当s target时将当前窗口内的连续整数存入数组并加入结果列表随后移动左边界并更新s。当s target时移动左边界缩小窗口并更新s。当s target时移动右边界扩大窗口并更新s。终止条件由于题目要求至少两个数循环在i j时终止。复杂度分析时间复杂度O(target)最坏情况下左右指针各遍历一次。空间复杂度O(1)不考虑输出结果的空间占用。代码实现import java.util.ArrayList; import java.util.Arrays; public class Solution { public int[][] fileCombination(int target) { int i 1; int j 2; int s 3; ArrayListint[] list new ArrayList(); while (i j) { if (s target) { int[] arr new int[j - i 1]; for (int k i; k j; k) { arr[k - i] k; } list.add(arr); s - i; i; } else if (s target) { s - i; i; } else { j; s j; } } return list.toArray(new int[0][]); } }示例说明输入target 9时输出[[2, 3, 4], [4, 5]]对应2349和459。注意事项右边界j每次移动时需累加到s。左边界i移动时需从s中减去。结果转换为二维数组时使用list.toArray(new int[0][])保证类型安全。题目链接 https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/