Leetcode每日一题：使数组和能被 P 整除的解法与优化

Leetcode每日一题 —— 1590. 使数组和能被 P 整除

思路
第一反应是前缀和，但是不适用，大概率会超时。但可以通过余数来加速这个过程，先求出总和，减去需要减去的相应余数的最小子数组即可。举个例子示例一：总和10，10%6=4，我只要把前面队列中余数4的子数组去掉即可。

代码

        int idx = new int[p];
        Arrays.fill(idx, -1);
        int n = nums.length;
        long sum = 0;
        int ans = Integer.MAX_VALUE;
        for (int num : nums) {
            sum += num;
        }
        int add = (int) (sum % p);
        if (add == 0) return 0;
        long pre = 0;
        for (int i = 0; i < n; i++) {
            pre += nums[i];
            int mod = (int) (pre % p);
            idx[mod] = i;
            int l = idx[(mod + p - add) % p];
            if (pre == sum && l < 0 && ans == Integer.MAX_VALUE) return -1;
            if (mod == add || l >= 0) {
                ans = Math.min(ans, i - l);
            }
        }
        return ans;
    }

优化思路
没想到时间不知道有没有问题，但是内存居然超了！！！按理解这个不会吵的，把int改成HashMap试试看。

代码

        HashMap<Integer, Integer> idx = new HashMap<>();
        int n = nums.length;
        long sum = 0;
        int ans = Integer.MAX_VALUE;
        for (int num : nums) {
            sum += num;
        }
        int add = (int) (sum % p);
        if (add == 0) return 0;
        long pre = 0;
        for (int i = 0; i < n; i++) {
            pre += nums[i];
            int mod = (int) (pre % p);
            idx.put(mod, i);
            int l = idx.getOrDefault((mod + p - add) % p, -1);
            if (pre == sum && l < 0 && ans == Integer.MAX_VALUE) return -1;
            if (mod == add || l >= 0) {
                ans = Math.min(ans, i - l);
            }
        }
        return ans;
    }

后记
过了，速度还不错，不过还是对第一次提交内存超了这个事有点难以理解。