This is the second day of my participation in Gwen Challenge

Today’s topic is a comprehensive survey topic. I suggest you submit it by hand with me to feel and better understand prefix and algorithm application.

Topic describes

Given an integer array nums and an integer k, write a function to determine whether the array contains contiguous subarrays that satisfy both of the following conditions:

The size of the subarray must be at least 2 and the sum of the subarray elements must be a multiple of K. Return true if it exists; Otherwise, return false.

If there is an integer n such that the integer x conforms to x = n * k, x is said to be a multiple of k.

Example 1: input: nums = [23,2,4,6,7], k = 6 output: true explanation: [2,4] is a subarray of size 2, and the sum is 6. Source: the power button (LeetCode) link: https://leetcode-cn.com/problems/continuous-subarray-sum copyright shall belong to the collar of the network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This is a medium difficulty problem, the meaning is easy to understand, first can be solved by the naive method. Enumerating all subarrays, because the problem only needs the sum of subarrays, naturally thought of using prefixes and improve efficiency.
  • Prefix and is a kind of predictive calculation, common implementation code is as follows:
        int[] preSum = new int[n];
        preSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
Copy the code

AC code

public class DayCode {
    public static void main(String[] args) {

        int[] nums1 = new int[] {23.2.4.6.6};
        int k1 = 7;

        boolean ans1 = new DayCode().checkSubarraySum1(nums1, k1);
        System.out.println(ans1);

        boolean ans2 = new DayCode().checkSubarraySum2(nums1, k1);
        System.out.println(ans2);
    }


    /** * Time complexity O(n * n) * space complexity O(n) **@param nums
     * @param k
     * @return* /
    public boolean checkSubarraySum1(int[] nums, int k) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 2; j < n; j++) {
                if ((preSum[j] - preSum[i]) % k == 0) {
                    return true; }}}return false;
    }


    /** * Time complexity O(n) * space complexity O(n) **@param nums
     * @param k
     * @return* /
    public boolean checkSubarraySum2(int[] nums, int k) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int preSum = 0;
        int remainder = 0;
        for (int i = 0; i < n; i++) {
            preSum += nums[i];
            remainder = preSum % k;
            if (map.containsKey(remainder)) {
                if (i - map.get(remainder) >= 2) {
                    return true; }}else{ map.put(remainder, i); }}return false; }}Copy the code

conclusion

  • The time complexity of algorithm 1 in the above code is O(n * n) and the space complexity is O(n).
  • The time complexity of algorithm two in the above code is O(n * n), and the space complexity is O(n).
  • Algorithm two is the optimal solution of this problem. This solution comes from the official problem solution and adopts hashmap, prefix and congruence mathematical ideas to solve the problem cooperatively.
  • This kind of topic is more common in the actual investigation, combined with many knowledge points, comprehensive solution. More practice, can master better!
  • Stick to the daily question, come on!