Subarray Sum

Easy Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Thoughts

傻办法需要三循环， $O(n^3)$ 。我们可以先存一个preSum数组，用来存储到从0到i-1时数组和是多少。那么为子数组为０相当于说preSum中两个成员的值相等，这两个值之所夹的子数组即所求。

Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        Map<Integer, Integer> preSum = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        preSum.put(0, -1); // to handle cases like [-1, 1]
        for (int i = 0, sum = 0; i < nums.length; i++) {
            sum += nums[i];
            if (preSum.containsKey(sum)) {
                res.add(preSum.get(sum) + 1);
                res.add(i);
                return res;
            } else {
                preSum.put(sum, i);
            }
        }

        return res;
    }
}

Anlysis

TC: O(n)

SC: O(n)

PreviousPresum Next1352. Product of the Last K Numbers

Last updated 6 years ago

Was this helpful?

Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        Map<Integer, Integer> preSum = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        preSum.put(0, -1); // to handle cases like [-1, 1]
        for (int i = 0, sum = 0; i < nums.length; i++) {
            sum += nums[i];
            if (preSum.containsKey(sum)) {
                res.add(preSum.get(sum) + 1);
                res.add(i);
                return res;
            } else {
                preSum.put(sum, i);
            }
        }

        return res;
    }
}