題目鏈接

一維前綴和思想：$sum[i]$ = $sum[i?1]$ + $a[i]$

sum[l] - sum[l-2] [l-2,l] 區間內的數是 k 的倍數 sum[l] - sum[l-3] [l-3,l] 區間內的數是 k 的倍數 sum[l] - sum[l-4] [l-4,l] 區間內的數是 k 的倍數 ... ... ... sum[l] - sum[1] [1,l] 區間內的數是 k 的倍數 sum[l] - sum[0] [0,l] 區間內的數是 k 的倍數

($s_k$ - $s_{k?n}$)%$k$ == 0 等價于 $s_k$%$k$ = $s_{k?n}\%k$

時間復雜度 $O(n)$，空間復雜度 $O(n)$

class Solution { public:bool checkSubarraySum(vector<int>& nums, int k) {int n = nums.size();vector<int> sum(n+1);for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + nums[i-1];unordered_set<int> hash;for(int i = 2; i <= n; i++){hash.insert(sum[i-2]%k);if(hash.count(sum[i]%k)) return true;}return false;} };

總結

以上是生活随笔為你收集整理的Leetcode 523 连续的子数组和 前缀和 + 哈希表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。