力扣 – 劍指 Offer 57 – II. 和為s的連續正數序列

• 2021 年 10 月 30 日
• 筆記
• 雙指針, 數組, 滑動窗口, 演算法

題目

劍指 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)\)