阿_D:/**解法2
* 若 (a[i]+a[i+1]+...+a[j])%5=0,
* 则有 (a[0]+a[1]+...+a[j])%k = (a[0]+a[1]+...+a[i-1])%k
* @param a 输入序列
* @param k mod值
* @return 最大子序列长度
*/
private static int findLargeSeq2(int[] a, int k) {
int sum = 0;
Map<Integer, Integer> candidates = new HashMap<>();
candidates.put(0, -1); //初始为0
int result = 0;
for(int i=0;i<a.length;i++){
sum += a[i];
if (!candidates.containsKey(sum%k)) {
candidates.put(sum%k, i);
}else {
//return Arrays.copyOfRange(a, candidates.get(sum%k)+1, i+1);
int temp = i-candidates.get(sum%k);
if (temp>result) {
result = temp;
}
}
}
return result;
}
//解法1:遍历所有的子序列,滑动窗口的思想
private static int findLargeSeq1(int[] a, int k) {
int len = a.length;
int result = 0;
for(int i=0;i<len;i++){
int sum = 0;
for(int j=i;j<len;j++){
sum +=a[j];
if (sum%5==0) {
if ((j-i+1)>result) {
result = j-i+1;
}
}
}
if (result>=len-i) {
break;
}
}
return result;
}

0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了: