算法刷题-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);
    }
}