首页 > 代码库 > 求最大子串和 最长子串的java写法
求最大子串和 最长子串的java写法
同事去面试问到求最大和的子串，举例来说给你一个有正有负的数组， 1 -1 2 -4 5 6 -3，它的最大和就是 5 6 所组成的子串和11。根据其隔离性，即任何子串内部都不会有这样一个结构 2 -4，因为如果包含这个子串，必定不是最大子串（2-4<0）,因此可以根据此性质，将数组进行分割，而分割的标志就是小于0的结构。
1 public static void main(String[] args) { 2 3 int[] array = {1,2,-4,3,5,-4,7,8,2,-1,6,-5,-200,3,47,-2}; 4 5 System.out.println(findMaxValue(array)); 6 7 //寻找最大子串 8 int [] subArray = findMaxSubArray(array); 9 for(int tmp : subArray){10 System.out.print(tmp+ " ");11 }12 13 }14 15 /**16 * @Description:找到最大子串和17 * @param array18 * @return19 * @returType:int20 */21 public static int findMaxValue(int[] array){22 int max = 0;23 int sum = 0;24 for(int i=0;i<array.length;i++){25 sum = sum + array[i];26 if(sum > max){27 max = sum;28 29 }else if(sum<0){30 sum = 0;31 }32 }33 return max;34 }35 36 /**37 * @Description:找到一个字符串的最大子串38 * @param array39 * @return40 * @returType:int[]41 */42 public static int[] findMaxSubArray(int[] array){43 int max = 0;44 int sum = 0;45 int start = 0;46 int end = 0;47 int tmpStart = 0;48 for(int i=0;i<array.length;i++){49 sum = sum + array[i];50 if(sum > max){51 max = sum;52 start = tmpStart;53 end = i;54 }else if(sum<0){55 sum = 0;56 tmpStart = i;57 }58 }59 return Arrays.copyOfRange(array, start+1, end+1);//截取不包括自己60 }
还有一种是求，给定一个数组，求数组中最长的子串，子串的头和尾是同一个数字。例如：1，2，3，4，2，4 2的间距是3
1 public static void main(String[] args) { 2 3 int[] array = {1,2,-4,3,5,-4,7,8,2,-1,6,-5,-200,3,47,-2}; 4 //寻找最长子串 5 int[] lenArray = findMaxLengthArray(array); 6 for(int tmp : lenArray){ 7 System.out.print(tmp+ " "); 8 } 9 10 }11 12 /**13 * @Description:求最长子串14 * @param array15 * @return16 * @returType:int[]17 */18 public static int[] findMaxLengthArray(int[] array){19 //key 放置数组的元素，value 第一个元素存放起始位置，第二个放置结束位置，第三个元素存放距离20 Map<Integer, Integer[]> map = new HashMap<Integer, Integer[]>();21 for(int i=0;i<array.length;i++){22 if(map.get(array[i])==null){23 Integer[] ints = new Integer[3];24 ints[0]=i;//初始位置25 ints[1]=i;//结束位置26 ints[2]=0;//初始长度27 map.put(array[i], ints);28 }else{29 map.get(array[i])[1]=i;30 map.get(array[i])[2]=i-map.get(array[i])[0];31 }32 }33 Iterator<Entry<Integer, Integer[]>> iterator = map.entrySet().iterator();34 int max = 0;35 int start = 0;36 int end = 0;37 int key = 0;38 while(iterator.hasNext()){39 Entry<Integer, Integer[]> entry = iterator.next();40 if(entry.getValue()[2]>max){41 max = entry.getValue()[2];42 start = entry.getValue()[0];43 end = entry.getValue()[1];44 key = entry.getKey();45 }46 }47 System.out.println("最大长度的数字是："+ key);48 System.out.println("最大长度为:"+max);49 return Arrays.copyOfRange(array, start+1, end+1);//截取不包括自己50 }
实际上使用了一个hashmap，value存储了开始位置，结束位置以及长度，因此一遍遍历数组，再一遍遍历hashmap就可以求出最长距离，Integer[] 改成hashmap效率会更高一些，时间复杂度为O(n)，空间复杂度高一些
求最大子串和 最长子串的java写法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。