1
\$\begingroup\$

According to LeetCode, the following question is one of the most frequent interview questions asked by companies such as Facebook and Google. Here, I'm posting C++/Java codes, if you'd like to review, please do so.

LeetCode 560

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

Example 1:

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

Constraints:

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

C++

class Solution {
public:
    int subarraySum(vector<int> &nums, int target) {
        map<int, int> prefix_sum;
        int sum = 0, subarrays = 0;
        prefix_sum[0]++;
        for (int index = 0; index < nums.size(); index++) {
            sum += nums[index];
            subarrays += prefix_sum[sum - target];
            prefix_sum[sum]++;
        }

        return subarrays;
    }
};

Java

class Solution {
    public int subarraySum(int[] nums, int target) {
        int sum = 0, subarrays = 0;
        Map<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0, 1);

        for (int index = 0; index != nums.length; index++) {
            sum += nums[index];

            if (prefixSum.get(sum - target) != null)
                subarrays += prefixSum.get(sum - target);

            prefixSum.put(sum, -~prefixSum.getOrDefault(sum, 0));
        }

        return subarrays;
    }
}

Reference

\$\endgroup\$
  • 2
    \$\begingroup\$ Please do not update the code in your question after receiving answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Jun 14 at 15:34
1
\$\begingroup\$

I have some suggestion for the Java version

Always try to pass the size of the maximum size to the Collection / Map constructor when known

The map has a default size of 16 elements, if you have more elements, the map will have to resize its internal cache. By setting the size, you can prevent the resize and make your code faster.

In this case, you can set the maximum size since it's based on the size of the array + 1.

Map<Integer, Integer> prefixSum = new HashMap<>(nums.length + 1);

Extract the expression to variables when used multiple times

In your code, when you check if the key is present, you can extract the value to a variable to reuse it when present.

Before

if (prefixSum.get(sum - target) != null)
   subarrays += prefixSum.get(sum - target);

After

Integer currentValue = prefixSum.get(sum - target);
if (currentValue != null)
   subarrays += currentValue;

This will be better, since this will prevent the rechecking and the rehashing in the map.

Always add curly braces to loop & if

In my opinion, it's a bad practice to have a block of code not surrounded by curly braces; I saw so many bugs in my career related to that, if you forget to add the braces when adding code, you break the logic / semantic of the code.

Before

if (prefixSum.get(sum - target) != null)
   subarrays += prefixSum.get(sum - target);

After

if (prefixSum.get(sum - target) != null) {
   subarrays += prefixSum.get(sum - target);
}

Extract some of the logic to methods.

In this case, I suggest to extract the map creation to a method; this will allow to group the logic and make the main code shorter.

public int subarraySum(int[] nums, int target) {
   Map<Integer, Integer> prefixSum = buildMap(lengthOfNums + 1);
   //[...]
}

private Map<Integer, Integer> buildMap(int defaultSize) {
   Map<Integer, Integer> prefixSum = new HashMap<>(defaultSize);
   prefixSum.put(0, 1);
   return prefixSum;
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ About those curly braces: you know what happens when you don't do that? Heartbleed. Very good advice to add those braces indeed. It doesn't fix everything (as indicated by that article), but it does make the bug more obvious. \$\endgroup\$ – Mast Jun 22 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.