JAVA DP solution with math prefixsum


  • 0
    T
     /**
         * using the math equation :
         * (prefixSum(j) - prefixSum(i))%k == 0 <=> prefixSum(j) % k - prefixSum(i) % k == 0
         * which the j - i > 1;
         * prefixSum(n) means the sum of 0 to n;
        */
        public boolean checkSubarraySum(int[] nums, int k) {
            Map<Integer,Integer> map = new HashMap<>();
            map.put(0,-1);//for the k = 0;
            int dpsum = 0;
            for (int i = 0; i < nums.length; i ++) {
                dpsum += nums[i];
                if (k != 0) {
                    dpsum %= k;
                }
                int t = map.getOrDefault(dpsum, i);
                map.put(dpsum, t);
                if (i - t > 1) {
                    return true;
                }
            }
            return false;
        }
    

Log in to reply
 

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