傾夢小筑

01. 審題

給定一個包含非負數的陣列（nums[]）和一個整數（k），編寫一個涵式判斷該陣列是否存在含有連續元素的子陣列，其長度至少為 2，所有元素總和為 k 的倍數，即總和為 n * k（ｎ 為整數）。

範例測試資料 1：

Input

nums = [23,2,4,6,7], k = 6

Output

true

範例解釋 1：

[2, 4] 為連續子陣列，長度為 2，加總為 6，可被 6 整除。

範例測試資料 2：

Input

nums = [23,2,6,4,7], k = 6

Output

true

範例解釋 2：

[23, 2, 6, 4, 7] 為連續子陣列，長度為 5，加總為 42，可被 6 整除。

範例測試資料 3：

Input

nums = [23,2,6,4,7], k = 13

Output

false

02 解法1（Java）

列舉所有加總，檢查是否符合條件即可。

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

然而送出後會因為測資過大導致 Timeout

03 解法2（Java）

此處需要一點數學：將數字 A 和 B 分别除以數字 C，若得到相同餘數，則 (A - B) 必能整除 C。

證明如下：

a % c = b % c  >> (a - b) % c = 0

a = mc + d;

b = nc + d;

a - b = (mc + d) - (nc + d)

        = mc - nc

        = (m - n)c

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map hashMap = new HashMap<>(Map.of(0, 0));
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            System.out.println(sum);
            if (!hashMap.containsKey(sum % k)) {
                hashMap.put(sum % k, i + 1);
            } else if (hashMap.get(sum % k) < i) {
                return true;
            }
        }
        
        return false;
     }
}

04. 結語

只想到了列舉法，優化後的解法是參考 LeetCode 解法QQ。