LeetCode 560 - Subarray Sum Equals K

https://leetcode.com/problems/subarray-sum-equals-k

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

X.

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/560_Subarray_Sum_Equals_K.java

    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ans = 0, sum = 0;
        for (int num : nums) {
            sum += num;
            ans += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }

https://zxi.mytechroad.com/blog/hashtable/leetcode-560-subarray-sum-equals-k/
Solution 1: Running Prefix sum

Keep tracking the prefix sums and their counts.

s -> count: how many arrays nums[0:j] (j < i) that has sum of s

cur_sum = sum(nums[0:i])

check how many arrays nums[0:j] (j < i) that has sum (cur_sum – k)

then there are the same number of arrays nums[j+1: i] that have sum k.

Time complexity: O(n)

Space complexity: O(n)

The idea behind this approach is as follows: If the cumulative sum(repreesnted by $sum[i]$ for sum upto $i^{th}$index) upto two indices is the same, the sum of the elements lying in between those indices is zero. Extending the same thought further, if the cumulative sum upto two indices, say $i$ and $j$ is at a difference of $k$ i.e. if $sum[i] - sum[j] = k$, the sum of elements lying between indices $i$ and $j$ is $k$.

Based on these thoughts, we make use of a hashmap $map$ which is used to store the cumulative sum upto all the indices possible along with the number of times the same sum occurs. We store the data in the form: $(sum_i, no. of occurences of sum_i)$. We traverse over the array $nums$ and keep on finding the cumulative sum. Every time we encounter a new sum, we make a new entry in the hashmap corresponding to that sum. If the same sum occurs again, we increment the count corresponding to that sum in the hashmap. Further, for every sum encountered, we also determine the number of times the sum $sum-k$has occured already, since it will determine the number of times a subarray with sum $k$ has occured upto the current index. We increment the $count$ by the same amount.

https://leetcode.com/problems/subarray-sum-equals-k/discuss/134689/Three-Approaches-With-Explanation

Solution3 - Remember the frequency of all prefix sums. O(n) time and O(n) memory.
sum to keep track of sum of all the elements so far. If we can find a prefix sum in the map for sum-k, it means we can form sum == k using the elements after the element corresponding to that prefix sum till the current element (included). Count all such sums at each element.

There is a special case like in the Solution2 when nums[x] == k that is current sum itself is equal to target without any subtractions. For this solution, we can either increment count by 1 whenever sum == k below or make an entry as a special case in our map
preSumFreq.put(0, 1) to cover those cases.

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

https://leetcode.com/problems/subarray-sum-equals-k/discuss/164431/Python-or-3-tm

还记得two sum这道题么？其实我们大可以把preSum作为我们字典中的key，然后value设置成为preSum出现次数，我们在迭代的时候，只需要查找preSum - target在不在字典里面，在的话，返回值增值即可，思路和two sum完全一样。这里我们字典里之所以存储出现次数，是为了解决出现重复数字的问题，比如
[0,0,0]这种case。

https://www.cnblogs.com/grandyang/p/6810361.html
论坛上大家比较推崇的其实是这种解法，用一个哈希表来建立连续子数组之和跟其出现次数之间的映射，初始化要加入{0,1}这对映射，这是为啥呢，因为我们的解题思路是遍历数组中的数字，用sum来记录到当前位置的累加和，我们建立哈希表的目的是为了让我们可以快速的查找sum-k是否存在，即是否有连续子数组的和为sum-k，如果存在的话，那么和为k的子数组一定也存在，这样当sum刚好为k的时候，那么数组从起始到当前位置的这段子数组的和就是k，满足题意，如果哈希表中事先没有m[0]项的话，这个符合题意的结果就无法累加到结果res中，这就是初始化的用途。上面讲解的内容顺带着也把for循环中的内容解释了
https://discuss.leetcode.com/topic/87850/java-solution-presum-hashmap

Solution 1. Brute force. We just need two loops (i, j) and test if SUM[i, j] = k. Time complexity O(n^2), Space complexity O(1). I bet this solution will TLE.

Solution 2. From solution 1, we know the key to solve this problem is SUM[i, j]. So if we know SUM[0, i - 1] and SUM[0, j], then we can easily get SUM[i, j]. To achieve this, we just need to go through the array, calculate the current sum and save number of all seen PreSum to a HashMap. Time complexity O(n), Space complexity O(n).

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

    public int subarraySum(int[] nums, int k) {
        int sum = 0, result = 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        
        for (int num : nums) {
            sum += num;
            result += preSum.getOrDefault(sum - k, 0);
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }   
        return result;
    }

http://bookshadow.com/weblog/2017/04/30/leetcode-subarray-sum-equals-k/

利用字典cnt统计前N项和出现的个数

遍历数组nums：

    在cnt中将sums的计数+1

    累加前N项和为sums

    将cnt[sums - k]累加至答案

https://leetcode.com/problems/subarray-sum-equals-k/discuss/134689/Three-Approaches-With-Explanation

Solution1 (TLE)
Basic brute-force approach - for all sum[i,j] count how many times we saw k. O(n^3).

public int subarraySum(int[] nums, int k) {
        int count = 0;
        for(int x=0; x < nums.length; x++){
            for(int y=x; y < nums.length; y++){
                int sum = 0;
                for(int z=x; z <= y; z++)
                    sum += nums[z];
                if(sum == k)
                    ++count;
            }
        }
        return count;
    }

Solution2 - make use of prefix sum for the third for-loop above. O(n^2)

public int subarraySum(int[] nums, int k) {
        int count = 0;
        for(int x=1; x < nums.length; x++)
            nums[x] += nums[x-1];
        for(int x=0; x < nums.length; x++){
            if(nums[x] == k)
                ++count;
            for(int y=x+1; y < nums.length; y++)
                if(nums[y]-nums[x] == k)
                    ++count;
        }
        return count;
    }

https://leetcode.com/articles/subarray-sum-equals-k/

  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 < nums.length; end++) {

        sum += nums[end];

        if (sum == k)

          count++;

      }

    }

    return count;

  }

  public int subarraySum(int[] nums, int k) {

    int count = 0;

    int[] sum = new int[nums.length + 1];

    sum[0] = 0;

    for (int i = 1; i <= nums.length; i++)

      sum[i] = sum[i - 1] + nums[i - 1];

    for (int start = 0; start < nums.length; start++) {

      for (int end = start + 1; end <= nums.length; end++) {

        if (sum[end] - sum[start] == k)

          count++;

      }

    }

    return count;

  }

  public int subarraySum(int[] nums, int k) {

    int count = 0;

    for (int start = 0; start < nums.length; start++) {

      for (int end = start + 1; end <= nums.length; end++) {

        int sum = 0;

        for (int i = start; i < end; i++)

          sum += nums[i];

        if (sum == k)

          count++;

      }

    }

    return count;

  }

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Positive%20Subarray%20Sum%20Equals%20K/PositiveSubarraySumEqualsK.java

public class PositiveSubarraySumEqualsK {

    public int subarrySum(int[] nums, int k) {
        if (k <= 0) return 0;
        int j = 0, sum = 0, ans = 0;
        for (int num : nums) {
            sum += num;
            while (sum > k) sum -= nums[j ++];
            if (sum == k) ans ++;
        }
        return ans;
    }