leetcode 剑指 Offer 57

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 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

解法一：dfs深度优先搜索

思路：

dfs深度优先搜索，每次添加之前先判断temp是否为空或者 temp 是是否包含 i - 1,

 1 class Solution {
 2     public int[][] findContinuousSequence(int target) {
 3         ArrayList<LinkedList<Integer>> res = new ArrayList<LinkedList<Integer>>();
 4         LinkedList<Integer> temp = new LinkedList<Integer>();
 5         // 使用dfs将所有的组合都找到并存在res列表中
 6         dfs(0, target, 0, res, temp);
 7         //System.out.println(res);
 8         // 将res中的内容拷贝到一个二维数组中
 9         int[][] ret = new int[res.size()][];
10         for(int i= 0; i < res.size(); i++){
11             ret[i] = new int[res.get(i).size()];
12             for(int j = 0; j < res.get(i).size(); j++){
13                 ret[i][j] = res.get(i).get(j);
14             }
15         }
16         return ret;        
17     }
18 
19     // dfs递归
20     public void dfs(int nowSum, int target, int nowNum, ArrayList<LinkedList<Integer>> res, LinkedList<Integer> temp){
21         if(nowSum == target){
22             res.add(new LinkedList<Integer>(temp));
23             return;
24         }
25         if(nowSum > target){
26             return;
27         }
28         // 尝试添加每个大于当前数字的元素
29         for(int i = nowNum + 1; i < target; i++){
30             //System.out.println(i);
31             // 只能是连续的数字组合
32             if((temp.isEmpty() || temp.contains(i-1)) && nowSum + i <= target){
33                 temp.addLast(i);
34                 dfs(nowSum + i, target, i, res, temp);
35                 temp.removeLast();  // 回溯之后消除上次添加元素的影响
36             }
37         }
38 
39     }
40 }

这个方法当target比较大的时候会超时，只通过了22个测试用例

解法二：迭代

思路：

迭代, 以1-target/2的所有元素为起点，寻找满足条件的组合

 1 class Solution {
 2     public int[][] findContinuousSequence(int target) {
 3         ArrayList<int[]> res = new ArrayList<>();
 4         
 5         int sum = 0, limit = target / 2;    // 因为最少两个数，所以上界为target / 2
 6         for(int i = 1; i <= limit; i++){
 7             for(int j = i; ; j++){
 8                 sum += j;
 9                 if(sum > target){
10                     sum = 0;
11                     break;
12                 }else if(sum == target){
13                     int[] arr = new int[j - i + 1];
14                     for(int k = i; k <= j; k++){
15                         arr[k-i] = k;
16                     }
17                     res.add(arr);
18                 }
19             }
20         }
21 
22         return res.toArray(new int[res.size()][]);        
23     }
24 }

leetcode运行时间为8ms, 空间为36.6MB

复杂度分析：

空间复杂度：除了存储结果的数组只需要常数个变量，所以空间复杂度为O(1)

解法三：滑动窗口

思路：

滑动窗口，这个解法其实是对上个解法的改进，当我们判断到[i,j+1]的元素之和已经大于 target了，解法二是直接从( i + 1)开始，加上(i + 2), 一直到下次sum 大于 target, 假设区间为 [i+1, k], 但是其实这个区间的[i+1,j]的和在上一次迭代的时候就已经求出来了，所以我们只需要在上一次迭代的sum减去 i, 然后从j开始累加，一直累加到k, 这样可以避免很多重复计算

 1 class Solution {
 2     public int[][] findContinuousSequence(int target) {
 3         ArrayList<int[]> res = new ArrayList<>();
 4         
 5         int sum = 0, limit = target / 2;    // 因为最少两个数，所以上界为target / 2
 6         int i = 1, j = 1;
 7         while(i <= limit){
 8             if(sum < target){
 9                 sum += j;
10                 j++;        // 右指针后移
11             }else if(sum > target){
12                 sum -= i;
13                 i++;        // 左指针右移
14             }else{
15                 int[] arr = new int[j-i];       // j还没被添加到sum中，所以区间大小为j - i
16                 for(int k = i; k < j; k++){
17                     arr[k-i] = k;
18                 }
19                 res.add(arr);
20                 sum -= i;
21                 i++;
22             }
23                
24         }
25 
26         return res.toArray(new int[res.size()][]);        
27     }
28 }

leetcode运行时间为：2ms, 空间为36.9MB

复杂度分析：

时间复杂度：右指针没有回溯，所以相当于两个指针都从 1增大到了 target/2, 所以时间复杂度为O(target)

空间复杂度：除了存储结果的数组只需要常数个变量，所以空间复杂度为O(1)