劍指Offer57.2——和為s的連續正數序列：思路分享
解題秘鑰：滑動視窗！！！
在腦海中幻想出一個連續正整數序列的陣列，分別設兩個指標，指向陣列的索引，這兩個索引中間的部分我們稱之為視窗！
這道題里，用這個視窗中數值相加的和與target作比較，每次經過判斷，視窗擴大或縮小
視窗定義為左閉右開，
設視窗的左右兩端分別為i,j，起始在1的位置，視窗不包含任何數，
這里的幻想指的是不用在代碼中創建出真實的陣列
代碼中有幾點需要注意：
- 視窗的擴大和縮小，都是同向的：當
sum+j時，j也要向后移；當sum-i時，i也要向后移動，不要忘了每次得到結果后，將視窗縮小 i的取值范圍：回圈的終止條件是i>target/2，因為一旦i大于target/2，說明視窗中后面的數一定大于target/2，sum一定大于target，由于target奇偶的原因，當i==target時，是可能有解的- 回傳值的問題：題目要求回傳值是二維陣列，而由于我們不能確定解的個數，需要先定義一個
List來接收，list接收的型別本身就是陣列（類比接收Integer），需要將list變成array（如果裝的是int，則toArray后就是int[]；如果裝的是int[]，則變后就是int[][]），最后再把List轉為陣列，需要用到toArray方法
arraylist.toArray(T[] arr)：其中引數為轉換的目標型別
在這道題中，就是二維陣列型別，因此我們先創建一個二維陣列T
代碼實作如下：
class Solution {
public int[][] findContinuousSequence(int target) {
int i=1, j=1;//視窗左右邊界
int sum=0;//用來與target比較
List<int[]> list=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;
}
list.add(arr);
//記錄一個結果之后，一定記得視窗右移
sum-=i;
i++;
}
}
int[][] T=new int[list.size()][];
return list.toArray(T);
}
}
《劍指Offer》中陣列相關的習題差不多了，鏈接奉上：
【Java實作】劍指offer03——找到陣列中的重復數字
【Java實作】劍指offer04——二維陣列中的查找（LeetCode240：搜索二維矩陣）
【Java實作】劍指offer29——順時針列印二維陣列（LeetCode54：螺旋矩陣）
【Java實作】劍指offer53.1——在排序陣列中查找數字（LeetCode34：在排序陣列中查找元素的起始位置）
【Java面試真題】劍指Offer53.2——0~n-1中缺失的數字（異或、二分兩種解法）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/245328.html
標籤：java
上一篇：python-資料分析-（11）pandas聚合函式、透視表、交叉表、表格合并常見操作
下一篇：急需解答。