未排序数组中累加和为给定值的最长子数组系列问题

题目

给定一个无序数组arr 其中元素可正、可负、可0。给定一个整数k，求arr所有的子数组中累加和为k的最长子数组长度。

解答

假设s(i)是子数组arr[0…i]的累加和,那么s(j)就代表arr[0…j]的累加和，那么可求得arr[j+1…i]=s(i)-s(j)。 流程：

初始化变量sum=0，表示从arr[0]一直加到arr[i]的累加和。初始化变量len，表示累加到和为k的最长子数组长度。设置一个map，用来记录出现过的sum值和的它出现的最早位置，即第一次出现的位置。key代表出现过的sum,value代表第一次出现的位置。令sum+=arr[i]，即s(i)，然后在map中查看是否出现过sum-k。 2.1 如果sum-k存在，则取出它首次出现的位置,假设为j，表示arr[0…j]=sum-k=s(j)。而根据之前的假设arr[j+1…i]=s(i)=s(j),此时sum=s(i),所以arr[j+1…i]=sum-(sum-k)=k。因为map的value记录的是最早出现的位置，所以此时arr[j+1…i]是以arr[i]结尾的所有子数组中，累加和为k的子数组中最长的，然后更新len。 2.2 如果sum-k，不存在，说明以arr[i]结尾的子数组中没有累加和为k的子数组继续重复2，直到遍历完。 根据arr[j+1…i]=s(i)-s(j),所以，如果从0开始遍历，会导致j+1>=1,这样就会把以arr[0]开始的子数组漏掉了，所以应该从-1位置开始累加，也就是开始遍历时把(0,-1)加入map，表示如果任何一个数都不加时，累加和为0。 比如数组[1,2,3,3],k=6,如果不加（0，-1）： ①sum=1，index=0，加入map,map=[(1,0)]; ②sum=3，index=1，加入map，map=[(1,0),(3,1)]; ③sum=6，index=2，加入map，map=[(1,0),(3,1),(6,2)]; ④sum=9，index=3，此时map包含sum-k，即3，所以此时len的长度更新为2，即子数组为[3,3]。很显然子数组[1,2,3]才是最长的。所以不加（0，-1）会出现这种情况。 如果加了(0,-1): ①sum=1，index=0，加入map,map=[(0,-1),(1,0)]; ②sum=3，index=1，加入map，map=[(0,-1),(1,0),(3,1)]; ③sum=6，index=2，此时map包含sum-k，即0，此时len的长度为3，即[1,2,3]; ④sum=9，index=3，此时map包含sum-k，即3，所以此时子数组为[3,3],长度是2，所以len=3；显然符合要求。 public static int maxLength(int[] arr, int k) { if (arr == null || arr.length == 0) { return 0; } Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); int len = 0; int sum = 0; for (int i = 0; i < arr.length; i++) { sum += arr[i]; if (map.containsKey(sum - k)) { len = Math.max(len, i - map.get(sum - k)); } if (!map.containsKey(sum)) { map.put(sum, i); } } return len; }

扩展问题1：给定一个无序数组arr 其中元素可正、可负、可0。求arr所有的子数组中正数与负数个数相等的最长数组长度。 解：将arr中的正数变为1，负数变为-1，0不变，然后求累加和为0的最长子数组。

public static int maxLength(int[] arr) { if (arr == null || arr.length == 0) { return 0; } Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); int len = 0; int sum = 0; for (int i = 0; i < arr.length; i++) { arr[i] = arr[i]>0?1:arr[i]<0?-1:0; sum += arr[i]; if (map.containsKey(sum)) { len = Math.max(len, i - map.get(sum)); } if (!map.containsKey(sum)) { map.put(sum, i); } } return len; }

控制问题2：给定一个无序数组arr 其中元素只能是1或者0。求arr所有的子数组中0和1个数相等的最长数组长度。 解：将arr中的0变为-1，1不变，然后求累加和为0的最长子数组。

public static int maxLength(int[] arr) { if (arr == null || arr.length == 0) { return 0; } Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); int len = 0; int sum = 0; for (int i = 0; i < arr.length; i++) { arr[i] = arr[i]==0?-1:arr[i]; sum += arr[i]; if (map.containsKey(sum)) { len = Math.max(len, i - map.get(sum)); } if (!map.containsKey(sum)) { map.put(sum, i); } } return len; }