523. Continuous Subarray Sum

前往題目

想法

• the sum of the elements of the subarray is a multiple of k: 判斷是否整除就好

思路

又是一題大家都說沒寫過怎麼可能在面試寫出來的題目😂

關鍵是建立prefixSum map，prefix sum -> index

1. 先加入0, -1到map裡，防止遇到0就以為是答案的edge case，因為至少要2個數字組合起來
2. 疊代給定的陣列，每次加上當前數字，並且計算當前總和mod k
3. 如果map裡沒有這個prefix sum就加入
4. 有的話看看當前的指針是否和map裡紀錄的index相差超過1，有就代表找到了

Code

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int total = 0;

        for (int i = 0; i < nums.length; ++i) {
            // 更新prefix sum
            total += nums[i];
            // 算餘數
            int r = total % k;

            // 如果沒找到餘數
            if (!map.containsKey(r)) {
                map.put(r, i);
            } else if (i - map.get(r) > 1) { // 找到餘數並且與當前相差超過1個位置
                return true;
            }
        }

        return false;
    }
}