Subarray Sum

https://leetcode.com/problems/continuous-subarray-sum/description/

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Thoughts

求是否存在连续子数组的和能够整除k. 那我们可以把所有可能的子数组和遍历一遍。

Code

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        if (k == 0) {
            for (int i = 1; i < n; i++) {
                if (nums[i] == 0 && nums[i - 1] == 0) {
                    return true;
                }
            }

            return false;
        }

        int[] sum = new int[n];
        sum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + nums[i];
            if (sum[i] % k == 0) {
                return true;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                if ((sum[j] - sum[i - 1]) % k == 0) {
                    return true;
                }
            }
        }

        return false;
    }
}

Analysis

Errors:

1. k = 0的情况没考虑

2. sum[i] % k == 0 没考虑

3. int j = i; j < n; j++ 顺序写反了

做题耗时20min

时间复杂度O(n^2).