小宝的幸运数组

绝地灬酷狼 2022-10-25 04:45 82阅读 0赞

# 小宝的幸运数组 #

[题目链接][Link 1]

### 题目描述 ###

对于小宝来说，如果一个数组的总和能够整除他的幸运数字k，就是他的幸运数组，而其他数组小宝都很讨厌。现在有一个长度为n的数组，小宝想知道这个数组的子数组中，最长的幸运子数组有多长。  
对于子数组的定义，如果可以通过从开头和从结束分别删除若干个（可以为零或全部，前后删除个数不必相同）元素来从数组b获得数组a，则称数组a是数组b的子数组。（子数组包含原数组，但不包含空串）

### 输入格式 ###

> 多组输入。第一行包含一个整数T(1≤T≤10)，表示有T组测试数据。  
> 每组测试数据包含两行，第一行包含两个整数n和k(1≤n≤105,1≤k≤105)，分别表示数组长度和小宝的幸运数字。第二行包含n个空格分隔的整数a1,a2,.,an(0≤ai≤10^9)，为数组的元素。

### 输出格式 ###

> 对于每组数据，输出和能被k整除的最长子数组的长度。如果没有这样的子数组，则输出−1。

### 示例 ###

输入

4
    3 3
    1 2 3
    3 5
    1 2 3
    3 7
    1 2 3
    1 6
    5

输出

3
    2
    -1
    -1

### 解题思路 ###

#### 前言 ####

首先,要掌握前缀和的概念,不明白这个概念的可以去自己百度搜索相关资料。在掌握前缀和的情况下需要掌握`(a-b)%k==a%k-b%k`的数学基本知识。在此基础上，我们只需要通过贪心算法求解即可。

#### 详解 ####

在掌握前言的基础上，我们在对前缀和求模的时候，将模的下标保存到哈希表(数组)中，一旦存在之后其他前缀和的模在哈希表中存在，则证明两个下标之间的数组内容和能够使得被k整除(查看前面的数学知识)。

#### 代码 ####

import java.io.*;
    import java.util.*;
    public class Main {
        
    	public static void main(String[] args) throws IOException {
        
    		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    		StreamTokenizer st=new StreamTokenizer(br);
    		PrintWriter pr=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    		st.nextToken();
    		int m=(int)st.nval;
    		while(m>0) {
        
    			m--;
    			st.nextToken();
    			int n=(int)st.nval;
    			st.nextToken();
    			int k=(int)st.nval;
    			int[] preSumMods=new int[n+1];
    			int[] greed=new int[k+1];
    			Arrays.fill(greed, -1);
    			greed[0]=0;
    			int res=-1;
    			//录入数据 并进行处理
    			for(int i=1;i<=n;i++) {
        
    				st.nextToken();
    				preSumMods[i]=(preSumMods[i-1]+(int)st.nval)%k;
    				if(greed[preSumMods[i]]!=-1) res=Math.max(res, i-greed[preSumMods[i]]);
    				else greed[preSumMods[i]]=i;
    			}
    			pr.println(res);
    		}
    		pr.flush();
    		return;
    	}
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/11746/B