Not smart solution, but easy to understand


  • 8
    public class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            if (nums == null || nums.length == 0)   return false;
            
            int[] preSum = new int[nums.length+1];
            
            for (int i = 1; i <= nums.length; i++) {
                preSum[i] = preSum[i-1] + nums[i-1];
            }
            
            for (int i = 0; i < nums.length; i++) {
                for (int j = i+2; j <= nums.length; j++) {
                    if (k == 0) {
                        if (preSum[j] - preSum[i] == 0) {
                            return true;
                        }
                    } else if ((preSum[j] - preSum[i]) % k == 0) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
    

  • 0
    B

    Easy to understand!
    I created a 2D array to save the sum result, and the system just told me 'Memory Limit Exceeded', your solution help me to modify my code!

    Thanks.


  • 0
    Y

    I had the same solution as yours, and it is a O(n^2) solution.


  • 0

    @yl right, that's why I said it's not a smart solution. Still need more pratice to come up with a better solution :)


  • 0
    R

    @benny201 Same here. I think around half of the 2D array is wasted anyway. Instead, I used a HashMap to track the progressive sum starting at each index (and also check if it is divisible by the k).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.