美团8.31机器学习与数据挖掘笔试，编程题第一题

/**解法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; }