Java技术第六期——算法题一道

前几天，老吴给了我们一道算法题：

int[] arr= {1,92,56,58,57,3,70,71,74,72,73,75,18};

找出以上数组中连续数字最多的子数组。

简单地说，就是通过程序找到最多连续数字的那一串数组，这些数字可以不按照顺序排列，但是必须要连在一起。

用肉眼可以看出答案，就是70，71，74，72，73，75这一串数组，它满足连续且相邻。

那么，怎么找到它？

最简单粗暴的方法就是找出所有子数组，然后挨个匹配。

不过这样有点儿麻烦。

我想到了一种简单一些的方法。

既然我们的目标是找到连续且相邻的子数组，那么要满足连续，数组中的某个数必须有一个与它相邻的数在数组中。

那么我们可以对数组中每个数进行判断，看是否有它相邻的数字在数组中。

//判断是否有该数周围的数字
public static boolean findAround(int a,List<Integer> list) {
      if(list.contains(a-1)||list.contains(a+1)) {
        return true;
      }
    return false;
  }

然后再列一个新的数列，记录下判断结果，如果有子数组，则将该位记为1，如果没有，则记为0。

List<Integer> list =new ArrayList<>();
for(int b:arr) {
      if(findAround(b,listarr)) {
        list.add(1);
      }else {
        list.add(0);
      }
    }

那么得到的数组如下：

int[] arr= {0,0,1,1,1,0,1,1,1,1,1,1,0};

这样，为0的我们可以不用再进行判断，因为肯定不会连续，只需要将所有为1的标记的子数组取出，判断是否满足条件。

根据这个数组，我们可以对原数组进行截取，获得满足条件的两个子数组：56、58、57和70，71，74，72，73，75

//数组的截取

public static List<List<Integer>> substring(List<Integer> listindex,int[] array){
    List<List<Integer>> lists=new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    for(int i=0;i<listindex.size();i++) {
      if(listindex.get(i)==0) {
        if(list.size()>0) {
          lists.add(list);
        }
        list = new ArrayList<>();
      }
      if(listindex.get(i)==1) {
        list.add(array[i]);
      }
    }
    return lists;
  }

最后将两个数组进行判断，如若最大值减去最小值+1等于数组的长度，那么就可以说明他们是连续的数组。

//判断是否连续
private static boolean isArrays(List<Integer> list1) {
    int max=0;
    int min=list1.get(0);
    for(Integer l :list1) {
      if(l>max) {
        max=l;
      }
      if(l<min) {
        min=l;
      }
    }
    if(max-min==list1.size()-1) {
      return true;
    }else {
      return false;
    }
  }

将数组及长度输出即可得到答案