【華為OD題庫-084】最長連續子序列-Java

題目

有N個正整數組成的一個序列。給定整數sum，求長度最長的連續子序列，使他們的和等于sum，返回此子序列的長度。如果沒有滿足要求的序列，返回-1。
輸入描述
第一行輸入是:N個正整數組成的一個序列
第二行輸入是:給定整數sum
輸出描述
最長的連續子序列的長度
備注
輸入序列僅由數字和英文逗號構成，數字之間采用英文逗號分隔。序列長度:1<=N<= 200
輸入序列不考慮異常情況
示例1:
輸入
1,2,3,4,2
6
輸出
3
說明
1,2,3和4,2兩個序列均能滿足要求，所以最長的連續序列為1,2,3，因此結果為3.
示例2:
輸入
1,2,3,4,2
20
輸出
-1
說明
沒有滿足要求的子序列，返回-1

思路

滑動窗口法，以示例數據為例：1 2 3 4 2，目標和targetSum為6
記i為窗口左邊界，j為窗口右邊界，輸入的數組為nums，初始和為curSum=nums[0]
如果curSum<targetSum，那么將j右移動，并更新當前curSum+=nums[++j]，先右移再更新，可能越界
如果curSum==targetSum，那么記錄此時窗口的長度：j-i+1
如果curSum>targetSum，那么i右移，并更新當前curSum-=nums[i–]，先更新再右移，不會越界
最后考慮窗口保證有效，i,j不得超過nums范圍，循環條件注意加上：i<=j，否則：1 2 3 4 2，目標和為0,無法通過。

題解

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;}
}