文章目錄

• 題目描述
• 思路 & 代碼
• • • 二刷

題目描述

• 花了不少時間來優(yōu)化= =，很好的一道用來理解滑動窗口的題～
  

思路 & 代碼

• 要點：為了 O(n) 復雜度，左右邊界都只能往右走
• 滑動窗口：存儲當前連續(xù)正數(shù)序列

class Solution {// 左邊界、右邊界都只能往右走 public int[][] findContinuousSequence(int target) {ArrayList<int[]> ans = new ArrayList<>();int left = 1, right = 1;int sum = 0;// 推論1：滿足題目要求的序列，最大開頭為 target / 2while(left <= target / 2){// 1. 增大窗口if(sum < target){sum += right++;}// 2. 縮小窗口：滿足則加入，然后找 left + 1 開頭的序列；否則直接尋找。else {// 序列滿足的情況：加入答案if(sum == target){int[] ansArray = new int[right - left];for(int i = 0; i < ansArray.length; i++){ansArray[i] = left + i;}ans.add(ansArray);}// 縮小sum -= left++;}}// 這行轉化代碼有必要記一下。。return ans.toArray(new int[ans.size()][]);} }

二刷

• 核心還是滑動窗口，注意維護。
• 數(shù)組的處理也要注意噢

class Solution {public int[][] findContinuousSequence(int target) {ArrayList<int[]> ans = new ArrayList<>();int left = 1, right = 1;int sum = 0;while(left <= target / 2) {if(sum < target) {sum += right++;}else {if(sum == target) {int[] arr = new int[right - left];for(int i = 0; i < arr.length; i++) {arr[i] = left + i;}ans.add(arr);}sum -= left++;}}return ans.toArray(new int[ans.size()][]);} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 57- II. 和为 s 的连续正数序列（Java、滑动窗口、二刷）的全部內容，希望文章能夠幫你解決所遇到的問題。

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