題目
有N個(gè)正整數(shù)組成的一個(gè)序列。給定整數(shù)sum，求長(zhǎng)度最長(zhǎng)的連續(xù)子序列，使他們的和等于sum，返回此子序列的長(zhǎng)度。如果沒(méi)有滿足要求的序列，返回-1。
輸入描述
第一行輸入是:N個(gè)正整數(shù)組成的一個(gè)序列
第二行輸入是:給定整數(shù)sum
輸出描述
最長(zhǎng)的連續(xù)子序列的長(zhǎng)度
備注
輸入序列僅由數(shù)字和英文逗號(hào)構(gòu)成，數(shù)字之間采用英文逗號(hào)分隔。序列長(zhǎng)度:1<=N<= 200
輸入序列不考慮異常情況
示例1:
輸入
1,2,3,4,2
6
輸出
3
說(shuō)明
1,2,3和4,2兩個(gè)序列均能滿足要求，所以最長(zhǎng)的連續(xù)序列為1,2,3，因此結(jié)果為3.
示例2:
輸入
1,2,3,4,2
20
輸出
-1
說(shuō)明
沒(méi)有滿足要求的子序列，返回-1
思路
滑動(dòng)窗口法，以示例數(shù)據(jù)為例：1 2 3 4 2，目標(biāo)和targetSum為6
記i為窗口左邊界，j為窗口右邊界，輸入的數(shù)組為nums，初始和為curSum=nums[0]
如果curSum<targetSum，那么將j右移動(dòng)，并更新當(dāng)前curSum+=nums[++j]，先右移再更新，可能越界
如果curSum==targetSum，那么記錄此時(shí)窗口的長(zhǎng)度：j-i+1
如果curSum>targetSum，那么i右移，并更新當(dāng)前curSum-=nums[i–]，先更新再右移，不會(huì)越界
最后考慮窗口保證有效，i,j不得超過(guò)nums范圍，循環(huán)條件注意加上：i<=j，否則：1 2 3 4 2，目標(biāo)和為0,無(wú)法通過(guò)。
題解
package hwod;
import java.util.Arrays;
import java.util.Scanner;
public class TheLongestContinueSubStr {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
int sum = sc.nextInt();
System.out.println(theLongestContinueSubStr(nums, sum));
}
private static int theLongestContinueSubStr(int[] nums, int sum) {
int i = 0, j = 0, res = -1;
int curSum = nums[0];
while (i <= j && i < nums.length && j < nums.length) {
if (curSum < sum) {
j++;
if (j < nums.length) curSum += nums[j];
} else if (curSum >= sum) {
if (curSum == sum) res = Math.max(res, j - i + 1);
curSum -= nums[i];
i++;
}
}
return res;
}
}
推薦
如果你對(duì)本系列的其他題目感興趣，可以參考華為OD機(jī)試真題及題解（JAVA），查看當(dāng)前專欄更新的所有題目。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-756469.html
說(shuō)明
本專欄所有文章均為原創(chuàng)，歡迎轉(zhuǎn)載，請(qǐng)注明文章出處：https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各類采集站皆不可信，搜索請(qǐng)謹(jǐn)慎鑒別。技術(shù)類文章一般都有時(shí)效性，本人習(xí)慣不定期對(duì)自己的博文進(jìn)行修正和更新，因此請(qǐng)?jiān)L問(wèn)出處以查看本文的最新版本。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-756469.html
到了這里，關(guān)于【華為OD題庫(kù)-084】最長(zhǎng)連續(xù)子序列-Java的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
