题目描述

最近经常做到这个题目，给一个array和k，求subarray的sum（或者product）有几个，有多长，sum等于K的有几个，sum 小于 K的有几个。sum等于K的subarray最长是多少，最短是多少，sum不大于K的最长是多少，sum不小于K的最短是多少。所以在这里把这些题目都总结一下

53 Maximum Subarray/152 Maximum Product Subarray

这两个是属于DP的，避免混淆视听，还是在这里提一下吧，时间$O(n)$ 空间$O(1)$

Java 代码

    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > 0) {
                nums[i] += nums[i - 1];
            }
            res = Math.max(res, nums[i]);
        }
        return res;
    }
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;
        int minValue = nums[0], maxValue = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int tmp1 = minValue * nums[i];
            int tmp2 = maxValue * nums[i];
            minValue = Math.min(nums[i], Math.min(tmp1, tmp2));
            maxValue = Math.max(nums[i], Math.max(tmp1, tmp2)); 
            res = Math.max(res, maxValue);
        }
        return res;
    }

209 Minimum Size Subarray Sum

给一个positive integer array 和 一个 int s, 找出最短的sum >= s 的subarray，万一没找到返回0。 双指针维护一个Deque,for循环里面每次都加，while里面判断是不是满足条件，每次满足条件就可以计算一下长度并且poll出一个来直到不满足条件为止，条件的意思就是sum >= k 时间复杂度$O(n)$

Java 代码

    public int minSubArrayLen(int s, int[] nums) {
        int res = nums.length + 1;
        int left = 0, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= s) {
                res = Math.min(res, i - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        while (sum >= s) {
            res = Math.min(res, nums.length - left);
            sum -= nums[left];
            left++;
        }
        if (res == nums.length + 1) return 0;
        return res;
    }

325. Maximum Size Subarray Sum Equals k

这道题和上一道很像，是找出sum为K的subarray的最大长度。但是和上一道不同的是，双指针维护Deque的方法在这里是不够的，因为array里面可能有负数，所以我们并不知道什么时候该poll出deque，就需要一个Map来记录preSum以及对应的index，注意这里是找max size，所以如果有相同的preSum我们并不更新map，这样能保证某一个PreSum对应的最靠前的index，如果题目问的是minSize，就应该改成需要更新map，这样每次map存的就是preSum对应的最靠后的index。

Java 代码

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

560. Subarray Sum Equals K

给一个int array 和一个int k，找出sum为k的subarray有多少个。
同样因为数组里面可能有负数和0，只能用一个Map来记录，但这次map记录的不是index，而是前面出现了多少个同样的preSum。每次都看一下map里面有没有sum-k，有的话就加上对应的count，然后吧此时的sum加到map里面，更新对应的次数。

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> preSumCount = new HashMap<>();
    preSumCount.put(0, 1);
    int res = 0, sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        Integer count = preSumCount.get(sum - k);
        if (count != null) {
            res += count;
        }
        preSumCount.put(sum, preSumCount.getOrDefault(sum, 0) + 1);
    }
    return res;
}

930. Binary Subarrays With Sum

给一个array A，只包含0和1，有多少个subarray的sum是S
常规方法是用map记录，每个preSum和它的count，然后用跟560一样的方法来做，但是因为这里只有0/1，还有另一种更好的解法，就是找出所有连续0的个数，不过这个方法对于S=0的情况要单独计算。

public int numSubarraysWithSum(int[] A, int S) {
        List<Integer> arr = new ArrayList<>();
        int zeroCount = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] == 1) {
                arr.add(zeroCount);
                zeroCount = 0;
            } else {
                zeroCount++;
            }
        }
        arr.add(zeroCount);
        int res = 0;
        if (S == 0) {
            for (int a:arr) {
                res += a * (a + 1) / 2;
            }
        } else {
            for (int i = 0; i < arr.size() - S; i++) {
                int leftZero = arr.get(i), rightZero = arr.get(i + S);
                res += (leftZero + 1) * (rightZero + 1);
            }
        }
        return res;
    }

713. Subarray Product Less Than K

这道题给的是positive int array 和K，方法就跟209很类似，用两个指针维护Deque，但是因为这里是less than K，所以每次都是把满足条件的deque的size加起来

public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0;
        int prod = 1;
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            prod *= nums[i];
            while (prod >= k && left <= i) {
                prod /= nums[left];
                left++;
            }
            res += i - left + 1;
        }
        return res;
    }

523. Continuous Subarray Sum

这道题也是思路类似的，positive array，是K的倍数。因此存的preSum每次都可以%k之后在更新map。

862 Shortest Subarray with Sum at Least K

最后这道还在思考中，没有想出很好的方法。根据之前的总结，因为有负数，肯定要用到map来记录preSum以及index，又因为需要shortest size， index是每次要更新的，难点在于，这个K并不是固定的，不像之前的几道题每次可以在map里面找有没有preSum-k，这里需要遍历map，来找到所有preSum - k >= 0 的情况然后选一个index相差最近的。但这样做就会超时。。。

最后做个小总结吧：
如果array里面只有正数，可以用双指针（也就是维护一个Deque）因为都是正数，preSum肯定是递增的，我们能很清楚的知道什么时候应该poll，什么时候还需要继续push。
总结起来就是，要找最大/小xize的，map里面存的是index，并且要根据是求最大还是最小来选择遇到同样的sum，map是否要更新。并且要一开始map.put(0, -1),代表一开始有一个sum为0的在-1处。如果是要找有多少个的，map里面存的就是sum以及对应的个数。每次都要更新。