本题为easy版本,和hard版本的唯一区别是保证是正整数! 小红拿到了一个数组,她想知道,有多少非空区间满足区间所有元素之和不小于?
区块链毕设网qklbishe.com为您提供问题的解答
本题为easy版本,和hard版本的唯一区别是保证是正整数!
小红拿到了一个数组,她想知道,有多少非空区间满足区间所有元素之和不小于?
题解笔记:
import java.util.Scanner; import java.util.Arrays; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); long k = in.nextLong(); long[] aArray = new long[n]; for(int i=0;i<n;i++){ aArray[i]=in.nextLong(); } long res=0; int left=0; long sum=0; for(int right=0;right<n;right++){ // right指针右滑 sum+=aArray[right]; while(sum >= k){ // [left,right], [left,right+1]...都符合条件 res+=(n-right); // left指针左滑 sum-=aArray[left]; left++; } } System.out.print(res); } }
参考自:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取 n 和 k int n = scanner.nextInt(); long k = scanner.nextLong(); // 读取数组 long[] arr = new long[n]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextLong(); } long count = 0; long currentSum = 0; int left = 0; // 双指针法,右指针从左到右移动 for (int right = 0; right < n; right++) { currentSum += arr[right]; // 当区间 [left, right] 的和不小于 k 时,移动左指针缩小窗口 while (currentSum >= k) { // 计算满足条件的区间数,右指针固定,左指针可以从 left 到 right。 count += (n - right); // 后续所有的区间 [left, right], [left+1, right], ... [right, right] 都满足 currentSum -= arr[left]; // 减去左端点的值 left++; // 移动左指针 } } // 输出结果 System.out.println(count); } }
12:43
以上就是关于问题本题为easy版本,和hard版本的唯一区别是保证是正整数! 小红拿到了一个数组,她想知道,有多少非空区间满足区间所有元素之和不小于?的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训