10.和为K的子数组

raylan.chen大约 3 分钟

class Solution {
    public int subarraySum(int[] nums, int k) {
        // dp[j] 代表包括nums[j]后尽量接近k的子数组和，i为子数组的起始位置
        // dp[j] = nums[j] || dp[i] + nums[j]
        
        if (nums.length == 1 && nums[0] == k) return 1;
        else if (nums.length == 1 && nums[0] != k) return 0;

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int i = 0;
        int j = 1;
        int res = 0;
        // [0, 0], k = 0
        if (nums[i] == k) res++;
        for (; j < nums.length; j++) {
            // [1, 1, 1, 2, 3, 4, 5, 6], k = 7
            // [-1, -1, 1], k = 0
            while (i < j
            && ((dp[j - 1] + nums[j] > k && nums[i] > 0)
            || (dp[j - 1] + nums[j] < k && nums[i] < 0))) {
                dp[j - 1] -= nums[i++];
            }
            dp[j] = dp[j - 1] + nums[j];
            if (dp[j] == k) {
                res++;
            }
            // [0, 0], k = 0
            if (i != j && nums[j] == k) res++;
        }
        while (i > 0) {
            dp[j - 1] += nums[--i];
            if (dp[j - 1] == k) res++;
        }
        return res;
    }
}

遇到输入：nums = [0,0,0,0,0,0,0,0,0,0], k = 0，输出：19，预期结果：55

优秀题解

枚举

假设遍历 nums 数组到索引为 j 的 nums[j]，随后以 j 为起点向前搜索是否含有 [i...j] 的子数组和 == k

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; ++start) {
            int sum = 0;
            for (int end = start; end >= 0; --end) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/238572/he-wei-kde-zi-shu-zu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在枚举的过程中，其实有部分操作是重复进行的；

例如：[1, 1, 1, 2, 3, 4, 5, 6], k = 7

假设数组索引为4，nums[j] = 3 时，

需要计算 3 =？k，3 + 2 =？k，3 + 2 + 1 =？k，3 + 2 + 1 + 1=？k，3 + 2 + 1 + 1 + 1=？k；

那么后续数组索引为5，nums[j] = 4时，

需要计算 4 =？k，4 + 3 =？k，4 + 3 + 2 =？k，4 + 3 + 2 + 1 =？k，4 + 3 + 2 + 1 + 1=？k，4 + 3 + 2 + 1 + 1 + 1=？k；

对比上述两个过程，可发现 3 + 2 ，3 + 2 + 1，3 + 2 + 1 + 1，3 + 2 + 1 + 1 + 1 可以存储其计算结果，以便后续重复利用；

这时其实可以使用一个容器存储前 i 个数相加的结果，pre[i] 代表 0~i 个数的累加和；

随后，找寻 4 + 3 =？k 的过程其实可以由 pre[5] - pre[3] =？k得到；

pre[j] - pre[i] =？k ==>可以转变为 pre[j] - k 是否存在？

为了快速找到是否含有 pre[j] - k 的元素，可以尝试使用 Set 或 Map存储 pre[j]；

如果使用 HashSet 存储，遇到 nums = [1,-1,0], k = 0，输出：2，但预期是 3；

1 + (-1) = 0，1 + (-1) + 0 = 0，nums[2] = 0。

// 尝试使用Set存储pre[j]
class Solution {
    public int subarraySum(int[] nums, int k) {
        // [1, -1, 0], k = 0, 输出：2，预期：3
        Set<Integer> set = new HashSet<>();
        int pre = 0;
        set.add(0);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            // nums[i] == k, pre[i] - k == pre[i - 1]
            if (set.contains(pre - k)) {
                count++;
            }
            set.add(pre);
        }
        return count;
    }
}

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > mp = new HashMap < > ();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
             // nums[i] == k, pre[i] - k == pre[i - 1]
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/238572/he-wei-kde-zi-shu-zu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

10.和为K的子数组

10.和为K的子数组

参考链接

个人尝试（❌错误）

优秀题解