LeetCode560. Subarray with and K

Ideas

The first thought is violence , A double loop yields all consecutive substrings , But most of them will be overtime . I didn't think of any other way . Read the explanation of the question , Learned the concept of prefix and , The sum of substrings here is equal to end Prefix and subtract start And . On the basis of prefix and , Combined with the hash To optimize , That is, the sum of two numbers .

There are two areas that need attention . One 、 The required prefix and may appear more than once , So every time you count . Two 、 Prefixes and are 0 It's also a situation , And it is necessary , Need to be manually added . For example, the target is 0.

subject

Given an array of integers and an integer  k, You need to find the neutralization of the array as  k  The number of successive subarrays of .

Example 1 :

 Input :nums = [1,1,1], k = 2
 Output : 2 , [1,1]  And  [1,1]  For two different situations .

Copy

explain :

1. The length of the array is [1, 20,000].
2. The elements in are arrays [-1000, 1000] , And integers  k  The range is  [-1e7, 1e7].

Related Topics

• Array
• Hashtable
• The prefix and
• 1078
• 0

Code

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

            // key The prefix and ,value Number of occurrences 
            Map<Integer, Integer> qzh = new HashMap<>(nums.length);
            //  The length of the substring is 0（ At the front of the bus string ）, Prefixes and are 0, Number of occurrences +1（ Originally 0）
            qzh.put(0, 1);
            //  The prefix and 
            int sum = 0;
            int res = 0;

            for (int num : nums) {
                sum += num;
                //  Find the prefix and 
                final Integer target = qzh.get(sum - k);
                if (target != null) {
                    res += target;
                }
                //  Save the current prefix and the number of occurrences 
                qzh.put(sum, qzh.getOrDefault(sum, 0) + 1);
            }
            return res;
        }

Copy

Post Views: 157