数组中元素只有1，-1，求和为0的最长子数组

淡淡的烟草味﹌ 2021-12-15 15:19 262阅读 0赞

这是算法题未排序数组中累加和为给定值的最长子数组系列问题的一种情况，数组元素只有1，-1，要求和为0的最长子数组。这道题的结果就是比较和为0的子数组长度，哪个最长，结果就是哪一个。例如：

![20190703082552162.png][]

这里最暴力的算法就是：从数组开始到结尾依次做遍历，每一趟遍历中，再计算累加和，结果为0则计算出一个长度，和默认的长度0对比，如果大于默认长度，那么默认长度设置为该长度，一直遍历到数组最后一个元素为止。

算法的代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

这种算法复杂度是O(n\*n)， 也是最简单明了的做法。

还有一种比较特殊技巧，就是只需要一趟累加，比如：

nums\[0\],  
nums\[0\]+nums\[1\],  
nums\[0\]+nums\[1\]+nums\[2\],  
nums\[0\]+nums\[1\]+...+nums\[n-1\]

虽然我们不能保证这中间的累加和一定会出现0，但是我们可以通过当前的累加和 和 已经计算过的累加和做一个减法，如果这个减法的结果正好是0，那么我们可以认为当前会有一个子数组满足累加和为0。算法的思路如下：

a=a,a+b=a,那么可以认为b=0。

这个算法里面，我们需要一个容器HashMap来保存已经计算过的累加和和下标位置。而且这个map中会有一个默认的元素(0,-1)，在这篇文章里的例子中，我们的map会先后存放：(0,-1),(1,0),(2,1),(3,2),(4,3)。

在本例中，通过该算法计算出累加和为2的一个最长子数组就是从开始到倒数第二个元素的位置：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1][]

算法的代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 2][]

完整代码如下：

package com.xxx.algorithm;
    
    import java.util.HashMap;
    
    public class MaxSubArray {
    
    	public static int maxSub(int[] nums,int k){
    		if(nums==null||nums.length==0){
    			return 0;
    		}
    		int length = 0;
    		int sum = 0;
    		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    		map.put(0, -1);
    		for(int i=0;i<nums.length;i++){
    			sum += nums[i];
    			if(map.containsKey(sum-k)){
    				length = Math.max(i-map.get(sum-k), length);
    			}
    			if(!map.containsKey(sum)){
    				map.put(sum, i);
    			}
    		}
    		return length;
    	}
    	
    	public static int maxSubArray(int[] nums,int k){
    		if(nums==null||nums.length==0){
    			return 0;
    		}
    		int sum = 0;
    		int length = 0;
    		for(int i=0;i<nums.length;i++){
    			for(int j=i;j<nums.length;j++){
    				sum = sum+nums[j];
    				if(sum==k&&(j-i>length)){
    					length = j-i+1;
    				}
    			}
    			sum=0;
    		}
    		return length;
    	}
    	
    	public static void main(String[] args) {
    		int[] nums = {1,1,1,1,-1,-1,-1,1,1,-1,1};
    		System.out.println("max-length:"+maxSub(nums,0));
    	}
    
    }

本例的代码是一个通用的算法代码，他不仅可以计算累加和为0的子数组，还可以计算累加和为任意数k的最长子数组。

[20190703082552162.png]: /images/20211215/5e047508bab2442fbe8e17c60c70d075.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: /images/20211215/e5c015e1bbbf4685a4413a439ddf9700.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1]: /images/20211215/0dea77a214fd46fab5a733c49a085941.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 2]: /images/20211215/2607a8ddd65842f5806356fe81fc7f90.png