描述

• 给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有连续子数组中累加和为k的最长子数组长度。
  保证至少存在一个合法的子数组。

方法一

思路

• 枚举法，暴力查找；
• 所谓的连续子数组是指对于一个数组arr，从下标i到下标j的一段数据构成的新数组，而为了找出连续子数组中累加和为k的最长子数组，可以遍历arr所有的连续子数组，并检查其是否满足累加和为k的条件，找出其中最长的子数组。
• 枚举连续子数组，对于其实位置下标i只需要从0开始，结束位置j则从下标i+1开始，双重循环遍历即可。
• 在枚举的过程中就可以计算累加和，找出满足条件的最长子数组。
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * max length of the subarray sum = k
     * @param arr int整型一维数组 the array
     * @param k int整型 target
     * @return int整型
     */
    public int maxlenEqualK (int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 符合条件的最长子数组长度
        int res = 0;
        int length = arr.length - 1;
        for(int i = 0;i < length;++i){
            int sum = arr[i];
            for (int j = i+1;j < arr.length;++j){
                // 若和为给定值，则取最大子数组长度
                if (sum == k){
                    int count = j - i;
                    res = Math.max(count,res);
                }
                // 继续计算累加和
                sum += arr[j];
            }
            if (sum == k){
                int count = arr.length - i;
                res = Math.max(count,res);
            }
        }
        return res;
    }
  }

• 时间复杂度：,双重遍历；
• 空间复杂度：，常数级空间复杂度。

  方法二

  思路

• 哈希
• 方法一的时间复杂度为，有点慢，处理较大的数据比较吃力，所以需要降低算法的时间复杂度。
• 其实在方法一中有很多次重复计算，譬如说，在计算了1~4的连续子数组的累加和后，计算1~5的连续子数组同样计算了一遍1~4的累加和，浪费资源，所以需要考虑将之前计算的数据记录下来，以减少之后累加和计算所耗费的时间。
• 令S(i)表示0~i的累加和，S(j)则表示0~j的累加和，则j+1~i的累加和为S(i)-S(j)。
  
• 故可以计算S(i)，并使用hash数组来存储记录S(i)；因为要找出累加和为k的连续子数组，而当前已经知道S(i)，那么我只需要查看hash记录中是否存在S(i)-k这么一个数值，若是存在，则找出出现最早的下标j，，即连续子数组j+1~i满足题目要求，所以我们只需要依据上述操作，找出所有满足条件的连续子数组，并求出其中的连续最长子数组长度即可。
  
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * max length of the subarray sum = k
     * @param arr int整型一维数组 the array
     * @param k int整型 target
     * @return int整型
     */
    public int maxlenEqualK (int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        // 最长子数组长度
        int res = 0;
        // 累加和
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            int temp = sum - k;
            if (map.containsKey(temp)) {
                res = Math.max(res, i - map.get(temp));
            }
            // 记录累加和
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return res;
    }
  }

• 时间复杂度：，一层循环，遍历n个数据；
• 空间复杂度：，使用hash数组存储累加和。