LeetCode - Continuous Subarray Sum

문제 설명

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

입출력 예시

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

제약사항

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

Solution

1. Brute Force

이중 for문을 순회하며 중첩된 합이 k의 multiple인지 체크
=> 시간 초과

import java.util.*;

class Solution {

   public boolean checkSubarraySum2(int[] nums, int k) {

        for (int i = 0; i < nums.length; i++) {
            int subArrSum = nums[i];
            
            for (int j = i+1; j < nums.length; j++) {
                subArrSum = subArrSum + nums[j];
                if (subArrSum==0 || subArrSum >= k && ((subArrSum % k) == 0)) {
                    return true;
                }
            }
        }
        return false;
    }
}

2. 다르게 풀기

• sum[i:j], i<j, 를 인덱스, i에서 j까지 해당하는 subarray의 합이라고 표현하면,
• 모든 subarray 집합 sum[i:j]은 sum1[0:j1] or sum1[0:j1] -sum2[0:j2] 로 표현
  ( j1 - j2 >=2 : subarray길이가 최소 2여야 하므로)
• (sum1[0:j1]-sum2[0:j2])%k = 0 이 성립하는 sum1과 sum2가 존재하면 된다.
• sum1[i:j]%k = sum2[i2:j2]%k

   public boolean checkSubarraySumWithMod(int[] nums, int k) {
    
         HashMap<Integer,Integer> subArrSum= new HashMap<>();

         int accmulSum=nums[0];
         subArrSum.put(accmulSum%k,0);
         for (int i = 1; i < nums.length; i++) {
             accmulSum=accmulSum+nums[i];
             int mod = accmulSum % k;
             if (mod == 0) {
                 return true;
             }
             if (subArrSum.containsKey(mod) && i - subArrSum.get(mod) >= 2) {
                 return true;
             }
             subArrSum.putIfAbsent(mod, i);
         }
         return false;
    }