LeetCode——和等于 k 的最长子数组长度

Q：给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
注意:
?nums 数组的总和是一定在 32 位有符号整数范围之内的。

示例 1:
输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
示例 2:
输入: nums = [-2, -1, 2, 1], k = 1
输出: 2
解释: 子数组 [-1, 2] 和等于 1，且长度最长。

进阶:
你能使时间复杂度在 O(n) 内完成此题吗?

A：

1. 我觉得我有毛病，我竟然第一时间用递归……不过就算用了memo，也超时了

    private int len = 0;
    private Set<String> set;

    public int maxSubArrayLen(int[] nums, int k) {
        if (nums.length == 0)
            return 0;
        set = new HashSet<>();
        sum(nums, k, 0, 0, nums[0]);
        return len;
    }

    private void sum(int[] nums, int k, int left, int right, int count) {
        String s = left + "+" + right;
        if (set.contains(s) || right < left)
            return;
        set.add(s);
        if (count == k) {
            len = Math.max(len, right - left + 1);
        }
        sum(nums, k, left + 1, right, count - nums[left]);
        if (right + 1 < nums.length)
            sum(nums, k, left, right + 1, count + nums[right + 1]);
    }

2. 前缀和+map
   计算出每个索引的前缀和，利用HashMap储存每个前缀和和对应的索引，如果出现前缀和相同的情况，则储存较小的索引（因为要求最长子数组）；利用一个指针i作为子数组的结尾从后向前遍历（从前往后要判断索引位置在当前位置的前还是后，从后往前无需判断，因为如果在后为负），寻找map中是否储存有key为sum[i] - k的索引，如果有则更新max。当指针的值小于等于max的值后，则无需再继续遍历。

    public int maxSubArrayLen(int[] nums, int k) {
        if (nums.length == 0)
            return 0;
        int maxLen = 0;
        int[] sums = new int[nums.length + 1];
        sums[0] = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
            if (!map.containsKey(sums[i]))
                map.put(sums[i], i);
        }
        for (int i = sums.length - 1; i > maxLen; i--) {
            if (map.containsKey(sums[i] - k)) {
                maxLen = Math.max(maxLen, i - map.get(sums[i] - k));
            }
        }
        return maxLen;
    }

LeetCode——和等于 k 的最长子数组长度

原文：https://www.cnblogs.com/xym4869/p/13509217.html