【問題描述】[簡單]

【解答思路】

1. 滑動窗口

時間復雜度：O(N) 空間復雜度：O(1)

public int[][] findContinuousSequence(int target) {int i = 1; // 滑動窗口的左邊界int j = 1; // 滑動窗口的右邊界int sum = 0; // 滑動窗口中數字的和List<int[]> res = new ArrayList<>();while (i <= target / 2) {if (sum < target) {// 右邊界向右移動sum += j;j++;} else if (sum > target) {// 左邊界向右移動sum -= i;i++;} else {// 記錄結果int[] arr = new int[j-i];for (int k = i; k < j; k++) {arr[k-i] = k;}res.add(arr);// 左邊界向右移動sum -= i;i++;}}return res.toArray(new int[res.size()][]); }

2. 數學

public int[][] findContinuousSequence(int target) {int n = 2;int limit = target >> 1;LinkedList<int []> result = new LinkedList<>();while (true) {int numerator = 2 * target - n * n + n;int denominator = 2 * n;// 如果不是整除，我們需要略過。if (numerator % denominator != 0) {n++;continue;}int n1 = numerator / denominator;// n 如果大于于中間的數，等差數列公式可以明顯看到，得到的結果會大于target值； n1 不能為0，因為題目說明需要正整數；if (n >= limit || n1 <= 0) {break;}int[] a = new int[n];for (int k = n1, i = 0; i < n; i++, k++) {a[i] = k;}result.addFirst(a);n++;}return result.toArray(new int[result.size()][]);}

3.暴力

public int[][] findContinuousSequence(int target) {List<int[]> res = new ArrayList<>();if(target <= 2){return null;}for(int i = 1;i < target/2 + 1;i ++){int temp = target;int count = i;while(temp > 0){temp = temp - count;count++;}if(temp == 0){int[] arr = new int[count - i];int a = i;for(int j = 0;j < arr.length;j++){arr[j] = a;a++;}res.add(arr);}}return res.toArray(new int[0][]);}

【總結】

1.滑動窗口

2.數學是萬能的 沒有數學是萬萬不能的

3.細節

返回一個二重數組

List<int[]> res = new ArrayList<>(); int[] arr = new int[j-i]; return res.toArray(new int[res.size()][]); res.add(arr);

轉載鏈接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-yao-shi-hua-dong-chuang-kou-yi-ji-ru-he-yong-h/
轉載鏈接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-qi-lai-chu-zhong-de-shu-xue-jian-dan-yi-dong-b/
參考鏈接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/bao-li-fa-shuang-zhi-zhen-by-sugar-31/

總結

以上是生活随笔為你收集整理的[剑指offer]面试题第[57-2]题[JAVA][和为s的连续正数序列][数学法][滑动窗口]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。