poj 3061 快慢指针寻找最短区间

简介: 翻译过来简而言之就是第1行 输入测试的案例个数第 i 行 输入N和S (N代表数组长度,S代表目标和)寻找最短区间满足区间之和大于或者等于S第 i+1行 输入数组元素

题目

image.png

翻译过来简而言之就是

第1行 输入测试的案例个数

第 i 行 输入N和S (N代表数组长度,S代表目标和)

寻找最短区间满足区间之和大于或者等于S

第 i+1行 输入数组元素


思路

借助快慢指针 i 和 j ,i 在后,j 在前

满足区间之和的话,记录最短区间(j-i+1),刷新区间之和(sum -= a[i],i++ )

不满足区间之和,刷新区间(j++,sum += a[j] )

注意越界问题

尽管大部分测试用例可以通过,还是有一些看不到的奇葩测试,但做蓝桥杯的话,毕竟是按通过测试比例得分,也是值得借鉴的 ~

代码

输入过程都得老半天,恶心啊~ 😠


import java.util.Scanner;
//最短连续区间
public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//案例的个数
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
                int size = input.nextInt();
                int[] a = new int[size];
                int s = input.nextInt();
                for (int k = 0; k < size; k++) {
                    int num = input.nextInt();
                    a[k]=num;
                }
                ans[i]=check(a,s);
        }
        for (int an : ans) {
            System.out.println(an);
        }
    }
    public static int check(int[] a,int s){
        //快慢指针
        int i=0;
        int j=0;
        int min=999;
        int sum=a[0];
        while (j<a.length){
            int thisMin;
            if(sum>s){
                thisMin=j-i+1;
                if(thisMin<min){
                    min=thisMin;
                }
                sum-=a[i];
                i++;
                if(i>j){
                    if(i==a.length){//防止越界
                        break;
                    }
                    sum=a[i];
                    j++;
                }
            }
            if(sum==s){
                thisMin=j-i+1;
                if(thisMin<min){
                    min=thisMin;
                }
                sum-=a[i];//找到一个继续找下一个
                i++;
            }
            if(sum<s){
                j++;
                if(j==a.length){//防止越界
                    break;
                }
                sum+=a[j];
            }
        }
        return min;
    }
}
相关文章
|
1月前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
1月前
快慢指针之:链表中倒数第k个结点
快慢指针之:链表中倒数第k个结点
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
23天前
DAY-2 | 哈希表、指针与区间划分:字符种数统计问题
```markdown ## 题干 [牛客网链接](https://www.nowcoder.com/practice/eb94f6a5b2ba49c6ac72d40b5ce95f50) ## 题解 1. **查表法(哈希表)**:利用数组标记出现过的 ASCII 值小于127的字符,首次出现计数,重复则忽略。 2. **指针与区间划分(回头法)**:遍历字符串,对每个字符检查其前所有字符是否重复,重复则不计数。 ## 方法总结 - 哈希表在去重问题中非常实用,可多做相关练习。 - 使用`continue`时注意避免死循环,确保循环变量会改变。 - 多回顾此类问题以巩固理解。 ```
25 2
|
26天前
|
存储 机器学习/深度学习 人工智能
【算法基础】基础算法(三)--(双指针算法、位运算、离散化、区间合并)
【算法基础】基础算法(三)--(双指针算法、位运算、离散化、区间合并)
|
1月前
数据结构--链表刷题(一)快慢指针(下)
数据结构--链表刷题(一)快慢指针
18 0
|
1月前
数据结构--链表刷题(一)快慢指针(上)
数据结构--链表刷题(一)快慢指针
20 0
|
1月前
|
算法 C语言 索引
环形链表(快慢指针)
环形链表(快慢指针)
|
1月前
|
算法 Java
快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战
快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战
31 0
|
1月前
|
存储 算法
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)