举一反三: 最长连续子串问题

题目

给定一序列,如{1,2,3,4,5},求其连续子序列的和能被K整除的子序列的最长长度.

注: 连续子序列,即在序列中连续访问的数. 序列{1,2,3,4,5},其满足条件的序列为{2,3},{5},{1,2,3,4},{1,2,3,4,5},故满足条件的最长子序列为,{1,2,3,4,5},长度为5.

思路

思路1: 滑动窗口的思想,遍历全部子序列. 代码如下:

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

思路2: 数学思想

若(A[i]+A[i+1]+…+A[j])%K = 0. 则有 (A[0]+A[1]+….+A[j])%K = (A[0]+A[1]+…A[i-1])%K

通俗一点,就是若序列中存在被K整除的子序列,i->j,则0->j的序列mod K的结果和序列0->i-1 mod K的结果是相同的.

代码:

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

题2

求最长连续子序列的和等于K,子序列的最长长度

代码:

/** * 若 (a[i]+a[i+1]+...+a[j])=k, * 则有 (a[0]+a[1]+...+a[j]) = (a[0]+a[1]+...+a[i-1])+k * @param a 输入序列 * @param k 指定值 * @return 最大子序列长度 */ private static int findLargeSeq(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)) { candidates.put(sum, i); if (candidates.containsKey(sum-k)) { int temp = i-candidates.get(sum-k); if (temp>result) { result = temp; } } } } return result; }

题3

求最长连续子序列的和最大,子序列的最长长度

代码:

/** * 若 (a[i]+a[i+1]+...+a[j])=max, * 则有 (a[0]+a[1]+...+a[j]) = (a[0]+a[1]+...+a[i-1])+max * @param a 输入序列 * @return 最大子序列长度 */ private static int findLargeSeq(int[] a) { int sum = 0; TreeMap<Integer, Integer> candidates = new TreeMap<>(); candidates.put(0, -1); //初始为0 int result = 0; for(int i=0;i<a.length;i++){ sum += a[i]; if (!candidates.containsKey(sum)) { candidates.put(sum, i); } } result = candidates.get(candidates.lastKey()) - candidates.get(candidates.firstKey()); return result; }

注: TreeMap 根据key 自动升序.

参考文献

Subarray with sum divisible by kFind longest subarray whose sum is divisible by K