[LeetCode] 523. Continuous Subarray Sum

轉自LeetCode

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 the 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.

Note:

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

<Solution>
這題需要用到一個數學定理來解

如果 a / c 和 b / c 的餘數相同，則 (a - b) 一定可以被 c 整除

根據上面的定理，解題思路如下

• 歷遍 nums，並計算當下的總和

• 如果 table[ sum % k ] 存在，代表之前有一個 subarray 的和除以 k 的餘數，和目前的總和除以 k 的餘數相同，所以兩個和相減後所產生的和(等於某個 subarray 的和) 一定是 k 的倍數。因此，把 table 對應的 value，也就是該和最終所在的 index 相減，看看最後的 subarray 的 size 是否大於 2

• 如果 table[ sum % k ] 不存在，那麼記錄對應的 index

code 如下(參考資料)

C++

	class Solution {
	public:
	bool checkSubarraySum(vector<int>& nums, int k) {
	int sum = 0, key;
	int const len = nums.size();
	//>> key: sum
	//>> value: index
	unordered_map<int, int> table;
	table[0] = -1; //>> sum = 0 at index -1
	for(int i = 0; i < len; i++) {
	sum += nums[i];
	key = (k == 0) ? sum : sum % k;
	if(table.find(key) != table.end()) {
	if(i - table[key] > 1) {
	return true; //>> size is bigger than 2
	}
	}
	else {
	table[key] = i;
	}
	}
	return false;
	}
	};

view raw continuousSubarraySum.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public boolean checkSubarraySum(int[] nums, int k) {
	int sum = 0, key;
	final int len = nums.length;
	//>> key : sum
	//>> value : index
	HashMap<Integer, Integer> table = new HashMap<>();
	table.put(0, -1); //>> sum = 0 at index -1
	for(int i = 0; i < len; i++) {
	sum += nums[i];
	key = (k == 0) ? sum : sum % k;
	if(table.containsKey(key)) {
	if(i - table.get(key) > 1) {
	//>> size is bigger than 2
	return true;
	}
	}
	else {
	table.put(key, i);
	}
	}
	return false;
	}
	}

view raw continuousSubarraySum.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
	val map = mutableMapOf<Int,Int>()
	map[0] = -1
	var sum = 0
	var key = 0
	for(i in nums.indices) {
	sum += nums[i]
	key = sum % k
	if(map[key] == null) {
	map[key] = i
	} else if(i - map[key]!! > 1) {
	return true
	}
	}
	return false
	}
	}

view raw continuous_subarray_sum.kt hosted with ❤ by GitHub