Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/523.html

 523. Continuous Subarray Sum


 Given a list of non-negative numbers and a target integer k, write a function to check
 if the array has a continuous subarray of size at least 2 that sums up to a multiple of k,
 that is, sums up to n*k where n is also an integer.


 Example 1:

 Input: [23, 2, 4, 6, 7],  k=6
 Output: True
 Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.


 Example 2:

 Input: [23, 2, 6, 4, 7],  k=6
 Output: True
 Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.


 Constraints:
     The length of the array won't exceed 10,000.
     You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Algorithm

bruce force

note if k is 0 then mod will not work

Code

  • public class Continuous_Subarray_Sum {
        class Solution {
            public boolean checkSubarraySum(int[] nums, int k) {
    
                // input null check
    
                for (int i = 0; i < nums.length; ++i) {
                    int sum = nums[i];
                    for (int j = i + 1; j < nums.length; ++j) {
                        sum += nums[j];
                        if (sum == k) return true;
                        if (k != 0 && sum % k == 0) return true;
                    }
                }
    
                return false;
    
            }
        }
    }
    
    
    ############
    
    class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            Map<Integer, Integer> mp = new HashMap<>();
            mp.put(0, -1);
            int s = 0;
            for (int i = 0; i < nums.length; ++i) {
                s += nums[i];
                int r = s % k;
                if (mp.containsKey(r) && i - mp.get(r) >= 2) {
                    return true;
                }
                if (!mp.containsKey(r)) {
                    mp.put(r, i);
                }
            }
            return false;
        }
    }
    
  • // OJ: https://leetcode.com/problems/continuous-subarray-sum
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
      bool checkSubarraySum(vector<int>& nums, int k) {
        for (int i = 0; i < nums.size(); ++i) {
          int sum = nums[i];
          for (int j = i + 1; j < nums.size(); ++j) {
            sum += nums[j];
            if ((!k && !sum) || (k && sum % k == 0)) return true;
          }
        }
        return false;
      }
    };
    
  • class Solution:
        def checkSubarraySum(self, nums: List[int], k: int) -> bool:
            s = 0
            mp = {0: -1}
            for i, v in enumerate(nums):
                s += v
                r = s % k
                if r in mp and i - mp[r] >= 2:
                    return True
                if r not in mp:
                    mp[r] = i
            return False
    
    ############
    
    class Solution(object):
      def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if k == 0:
          return "0,0" in ",".join([str(n) for n in nums])
        if len(nums) < 2:
          return False
        if len(nums) == 2:
          return sum(nums) % k == 0
        ppSum = 0
        subSum = nums[0] + nums[1]
        d = set([0])
        for i in range(2, len(nums)):
          ppSum = (ppSum + nums[i - 2]) % k
          d |= {ppSum}
          subSum = (subSum + nums[i]) % k
          if subSum % k in d:
            return True
        return False
    
    
  • func checkSubarraySum(nums []int, k int) bool {
    	mp := map[int]int{0: -1}
    	s := 0
    	for i, v := range nums {
    		s += v
    		r := s % k
    		if j, ok := mp[r]; ok && i-j >= 2 {
    			return true
    		}
    		if _, ok := mp[r]; !ok {
    			mp[r] = i
    		}
    	}
    	return false
    }
    
  • class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            int length = nums.length;
            if (length < 2)
                return false;
            if (k == 0) {
                for (int i = 1; i < length; i++) {
                    if (nums[i - 1] == 0 && nums[i] == 0)
                        return true;
                }
                return false;
            }
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            map.put(0, -1);
            int remainder = 0;
            for (int i = 0; i < length; i++) {
                remainder = (remainder + nums[i]) % k;
                if (map.containsKey(remainder)) {
                    int prevIndex = map.get(remainder);
                    if (i - prevIndex > 1)
                        return true;
                } else
                    map.put(remainder, i);
            }
            return false;
        }
    }
    
    ############
    
    class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            Map<Integer, Integer> mp = new HashMap<>();
            mp.put(0, -1);
            int s = 0;
            for (int i = 0; i < nums.length; ++i) {
                s += nums[i];
                int r = s % k;
                if (mp.containsKey(r) && i - mp.get(r) >= 2) {
                    return true;
                }
                if (!mp.containsKey(r)) {
                    mp.put(r, i);
                }
            }
            return false;
        }
    }
    
  • // OJ: https://leetcode.com/problems/continuous-subarray-sum
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
      bool checkSubarraySum(vector<int>& nums, int k) {
        for (int i = 0; i < nums.size(); ++i) {
          int sum = nums[i];
          for (int j = i + 1; j < nums.size(); ++j) {
            sum += nums[j];
            if ((!k && !sum) || (k && sum % k == 0)) return true;
          }
        }
        return false;
      }
    };
    
  • class Solution:
        def checkSubarraySum(self, nums: List[int], k: int) -> bool:
            s = 0
            mp = {0: -1}
            for i, v in enumerate(nums):
                s += v
                r = s % k
                if r in mp and i - mp[r] >= 2:
                    return True
                if r not in mp:
                    mp[r] = i
            return False
    
    ############
    
    class Solution(object):
      def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if k == 0:
          return "0,0" in ",".join([str(n) for n in nums])
        if len(nums) < 2:
          return False
        if len(nums) == 2:
          return sum(nums) % k == 0
        ppSum = 0
        subSum = nums[0] + nums[1]
        d = set([0])
        for i in range(2, len(nums)):
          ppSum = (ppSum + nums[i - 2]) % k
          d |= {ppSum}
          subSum = (subSum + nums[i]) % k
          if subSum % k in d:
            return True
        return False
    
    
  • func checkSubarraySum(nums []int, k int) bool {
    	mp := map[int]int{0: -1}
    	s := 0
    	for i, v := range nums {
    		s += v
    		r := s % k
    		if j, ok := mp[r]; ok && i-j >= 2 {
    			return true
    		}
    		if _, ok := mp[r]; !ok {
    			mp[r] = i
    		}
    	}
    	return false
    }
    

All Problems

All Solutions