因为被美团的大佬翻牌子了，所以内推直接免笔试进面试，恰巧今天遇到同学们答美团的笔试题，热爱OJ的我就参与了一发，战果还不错，2道题都轻松AC了。
接下来就和大家分享一下我的做题思路和代码，我觉得第一题还有改进的地方，希望大家不吝赐教，我也今晚好好想想有没有更优秀的解法。
序列中任意个连续的元素组成的子序列称为该序列的子串。
现在给你一个序列P和一个整数K，询问元素和是K的倍数的子串的最大长度。
样例输入：
[1,2,3,4,5]，整数K，满足条件的子串是{5},{2,3},{1,2,3,4},{1,2,3,4,5}。
那么答案就是5。如果这样的子串不存在，就输出0.
这道题和今年蓝桥杯上面的一道题很想（虽然我也没参加，只是自己随便做了做它的题）。适用动态规划，维护一个dp矩阵，每个元素是前面元素和%K的结果，注意，我们计算下一个元素时，只需要根据递推公式: dp[i] = (dp[i-1]+arr[i])%K;即可。比如[1,2,3,4,5]就会得到[1,3,1,0,0]。
这时候我们再根据这个dp矩阵来计算最大长度，dp矩阵中元素一定是0,1,...K-1.
先看0.为0就代表前面的元素和正好是K的倍数，那么我们寻找数组中最后一个0的位置，就是dp[i]=0的最长子串长度-1.
然后看1，我们找dp矩阵中第一1的位置j和最后一个1之间的位置k的差，这个差值就是dp[i]=1的最长子串长度。相当于前k项和-前j项和正好是K的倍数。
...
依次类推到K-1，每次都维护最长距离max。最终输出。
同时加入arr.length==0的判断。
package com.nowcoder.java; public class Meituan01 { public static void main(String[] args) { int[] arr={1,2,3}; int K = 5; System.out.println(cal(arr,K)); } public static int cal(int[] arr,int K){ if(arr.length==0) return 0; int max=0; int[] dp = new int[arr.length]; dp[0] = arr[0]%K; for(int i=1;i<dp.length;i++){ dp[i]=(dp[i-1]+arr[i])%K; } for(int i=0;i<dp.length;i++){ if(dp[i]==0) max=i+1; } for(int i=1;i<K;i++){ int pre = 0; int back = dp.length-1; while(dp[pre]!=i && pre<back) pre++; while(dp[back]!=i && back>pre) back--; int len=back-pre; if(len>max) max=len; } return max; } }
太长了我直接贴图。
这道题乍看很难，其实道理只有一个！
那就是：最大的那一个组的人数一定要比其余组的和大于等于即可！
package com.nowcoder.java; import java.util.Arrays; public class Meituan02 { public static void main(String[] args) { int N=2; int[] arr = new int[]{10,10,20}; System.out.println(check(arr,N)); } public static boolean check(int[] arr,int N){ if(N<=1) return false; Arrays.sort(arr); int sum = 0; for(int i=0;i<N-1;i++){ sum+=arr[i]; } if(sum>=arr[N-1]) return true; else{ return false; } } }
代码如上，
以上
