算法刷题-2025年03月01日

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class test_02_28 { //长度最小的子数组 找出总和大于等于target的长度最小的子数组 //target = 7, nums = [2,3,1,2,4,3] [1.2.2.3.3.4] public static int test1(int[] nums, int target){ //存储结果 List<Integer> res = new ArrayList<>(); Arrays.sort(nums); int sum = 0; for (int i=nums.length-1;i>=0;i--){ if (sum>=target){ return res.size(); }else{ res.add(nums[i]); } sum+=nums[i]; } return 0; } //长度最小的子数组-要连续 //[2,3,1,2,4,3] 7 //滑动窗口解法 public static int test2(int[] nums, int target){ int i=0; int j=0; int n=nums.length; int sum=0; int res = n+1; while (j<n&&i<n){ sum+=nums[j]; //发现累加数小于 target 将j往右走 寻求累加 if (sum<target){ j++; }else { //发现累加数大于等于target 此时要考虑左边的i能不能往右边移动 if (sum - nums[i] < target) { System.out.println(res); //不可以移动 //获取此时的值和原来的值做比较 res = Math.min(j - i + 1, res); } //继续下一轮 sum = sum - nums[i]; i++; j++; } } if (res==n+1){ return 0; }else{ return j-i+1; } } //长度最小的子数组 找出一个数组中值最大但是长度最小的子数组 public static void test3(int[] arr, int target){ int n = arr.length; //j用来一直往前走 int j=0; int i=0; //存储最大值 int max=0; //结果 int res = n+1; //开始循环 while (j<n){ //找出 if (max+arr[j]>=target){ res=Math.min(res,j-i+1); System.out.println(res); //将其加上来 if (max+arr[j]-arr[i]>=target){ max=max-arr[i]; i++; }else{ j++; } }else{ max=max+arr[j]; j++; } } System.out.println(res); } public static int test4(int[] arr, int target){ int n=arr.length; int i=0; int j=0; int res = n+1; int max=0; while (j<n){ max=max+arr[j]; //获取结果 while (i<=j&&max>=target){ res=Math.min(res,j-i+1); max=max-arr[i]; i++; } j++; } if (res==n+1){ return 0; }else{ return res; } } public static void main(String[] args) { test4(new int[]{1,2,3,4,5,6,7}, 7); } }