最長(zhǎng)連續(xù)子序列
題目描述
有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,2,3,4,2 |
| 輸出 | 3 |
| 說(shuō)明 | 1,2,3和4,2兩個(gè)序列均能滿足要求，所以最長(zhǎng)的連續(xù)序列為1,2,3，因此結(jié)果為3。 |
| 輸入 | 1,2,3,4,2 20 |
| 輸出 | -1 |
| 說(shuō)明 | 沒(méi)有滿足要求的子序列，返回-1 |
題目解析
- 使用雙指針找到對(duì)相鄰的數(shù)進(jìn)行求和。若和正確，那么就判斷長(zhǎng)度是否比前面出現(xiàn)的長(zhǎng)度都大，若大就進(jìn)行記錄。
- 若和大于，那么就證明該區(qū)間內(nèi)不存在目標(biāo)序列。左指針右移，臨和減掉移出的左側(cè)的那個(gè)。
- 若和小于，就證明該區(qū)間還可以往右擴(kuò)充，右指針右移，臨和加上移入的那一個(gè)。這樣就避免了在內(nèi)部在使用循環(huán)計(jì)算區(qū)間和了。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class T53 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int sum = Integer.parseInt(sc.nextLine());
List<Integer> numList = new ArrayList<>();
Arrays.stream(input.split(",")).forEach(s -> {
numList.add(Integer.parseInt(s));
});
int left = 0;
int right = 0;
int tempSum = numList.get(left);// 臨時(shí)的區(qū)間和
int len = -1;
while (right < numList.size()) {
if (tempSum < sum) {
right++;
if (right == numList.size())
break;// 超出了
tempSum += numList.get(right);
// System.out.println(tempSum);
} else if (tempSum > sum) {
tempSum -= numList.get(left);
left++;
} else {
// System.out.println(right - left + "-");
// System.out.println(right + "-----" + left);
if (len < right - left) {
len = right - left + 1;
}
tempSum -= numList.get(left);
left++;
}
}
System.out.println(len);
}
}
代碼運(yùn)行示意圖
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-485374.html
到了這里，關(guān)于華為OD機(jī)試之最長(zhǎng)連續(xù)子序列（Java源碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
