【力扣题解】1590. 使数组和能被 P 整除

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

文章目录

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析
    • 2、代码详解
  • 三、本题知识

一、题目

1、题目描述

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

2、基础框架

• Java版本框架代码如下：

class Solution {    public int minSubarray(int[] nums, int p) { }}

3、原题链接

1590. 使数组和能被 P 整除

二、解题报告

1、思路分析

       (1)定义一个数组，用来计算前i位数的和，每次计算后结果对p取余。
       (2)遍历sum数组，计算x（即(p - (sum[n] - sum[i]))%p）的值，x值的含义为i到n这段区间内还需要一个多大的数可以被p整除。（sum[n] - sum[i]为i到n这段区间的和）。每次遍历的时候判断map中是否包含x，若包含说明在0~i的区间内存在一段区间，该区间内的值的和与i到n这段区间的和 相加可以被p整除，所以只需要删除i - map.get(x)之间的元素即可。map的Key是前i个值的和，Value是前i个值的和的位置。每次遍历去ret的最小值。

2、代码详解

class Solution {    public int minSubarray(int[] nums, int p) { int n = nums.length; int ret = Integer.MAX_VALUE; HashMap<Integer,Integer> map = new HashMap(); int[] sum = new int[n + 1]; for(int i = 1;i <= n;i++) {     sum[i] = sum[i - 1] + nums[i - 1];     sum[i] %= p; } if(sum[n] == 0) {     return 0; } map.put(0,0); for(int i = 1;i <= n;i++) {     int x = (p - (sum[n] - sum[i]))%p;     if(map.containsKey(x)) {  ret = Math.min(ret,i - map.get(x));     }     map.put(sum[i],i); } if(ret == Integer.MAX_VALUE || ret == n) {     ret =  -1; } return ret;    }}

三、本题知识

数论+前缀和