1 前缀和 1 2 3 4 vector<int > prefSum {nums[0 ]}; for (int i = 1 ; i < nums.size (); ++i) { prefSum[i] += (nums[i] + prefSum.back ()); }
1546最大非重叠数组 1 题目 https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/submissions/
2 解题思路 最为关键的一句话：
前缀和，普通为o(n^2)，使用hash优化：
但是有一个问题，在下一次搜寻开始的时候，需要将上一次搜寻过程的hash清零，
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 class Solution {public : int maxNonOverlapping (vector<int >& nums, int target) int ans = 0 ; int st = 0 ; int ed = 0 ; int lastFoundEd = ed; while (st < nums.size ()) { ed = st; unordered_set<int > hash = {0 }; int curSumFromLastFoundEd = 0 ; while (ed < nums.size ()) { curSumFromLastFoundEd += nums[ed]; if (hash.count (curSumFromLastFoundEd - target)) { ++ans; st = ed; break ; } else { hash.insert (curSumFromLastFoundEd); } ++ed; } ++st; } return ans; } };
0560subArraySum 子数组和为k 1 题目 https://leetcode-cn.com/problems/subarray-sum-equals-k/
2 解题思路 前缀和，普通为o(n^2)，使用hash优化：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : int subarraySum (vector<int >& nums, int k) vector<int > prefSum (nums.size()) ; prefSum[0 ] = nums[0 ]; for (int i = 1 ; i < nums.size (); ++i) { prefSum[i] += (nums[i] + prefSum[i-1 ]); } int st = 0 ; int ed = 0 ; int ans = 0 ; int curSum = 0 ; std::unordered_map<int , int > hash; hash[0 ] = 1 ; while (ed < nums.size ()) { if (hash.find (prefSum[ed] - k) != hash.end ()) { ans += hash[prefSum[ed] - k]; } hash[prefSum[ed]]++; ++ed; } return ans; } };
1171移除和为0的子链表 1 题目： https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
2 解题思路： 个人暴力思路：
1 每次移除一个和为0的子数组，返回一个新的链表
2 重复上述过程直到没有和为0的子数组
前缀和思路参考：采用前缀和判断和为0方法 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution {public : ListNode* newHead; ListNode* removeZeroSumSublists (ListNode* head) { newHead = head; while (removeOneZeroSubList (newHead)){ } return newHead; } bool removeOneZeroSubList (ListNode* newHead) vector<int > valVec; ListNode* head = newHead; ListNode* p = head; while (p != nullptr ) { valVec.emplace_back (p->val); p = p->next; } size_t len = valVec.size (); vector<vector<int >> sumMat (len, vector <int >(len)); ListNode* stPtr = head; ListNode* lastStPtr = nullptr ; for (int st = 0 ; st < len; ++st) { sumMat[st][st] = valVec[st]; if (sumMat[st][st] == 0 ) { if (nullptr == lastStPtr) { this ->newHead = head->next; return true ; } lastStPtr->next = stPtr->next; return true ; } ListNode* edPtr = stPtr->next; for (int ed = st + 1 ; ed < len; ++ed) { sumMat[st][ed] = sumMat[st][ed-1 ] + valVec[ed]; if (sumMat[st][ed] == 0 ) { if (nullptr == lastStPtr) { this ->newHead = edPtr->next; return true ; } lastStPtr->next = edPtr->next; return true ; } edPtr = edPtr->next; } lastStPtr = stPtr; stPtr = stPtr->next; } return false ; } };
1292最大方块长度 1 题目 https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
2 解题思路
1 建立二维前缀和： 1 2 3 4 5 6 vector<vector<int >> preSum (m+1 , vector <int >(n+1 , 0 )); for (int i = 1 ; i < m+1 ; ++i) { for (int j = 1 ; j < n+1 ; ++j) { preSum[i][j] = preSum[i-1 ][j] + preSum[i][j-1 ] - preSum[i-1 ][j-1 ] + mat[i-1 ][j-1 ]; } }
2 遍历所有边长的正方形即可(每个正放形为起点加上边长)，遍历长度的过程可以通过二分搜索加速
值得思考的点：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 class Solution {public : int maxSideLength (vector<vector<int >>& mat, int threshold) int m = mat.size (); int n = mat[0 ].size (); vector<vector<int >> preSum (m+1 , vector <int >(n+1 , 0 )); for (int i = 1 ; i < m+1 ; ++i) { for (int j = 1 ; j < n+1 ; ++j) { preSum[i][j] = preSum[i-1 ][j] + preSum[i][j-1 ] - preSum[i-1 ][j-1 ] + mat[i-1 ][j-1 ]; } } int maxSquareLen = std::min (m, n); int stLen = 1 ; int edLen = maxSquareLen; int ans = 0 ; while (stLen <= edLen) { int len = (stLen + edLen) / 2 ; bool found = false ; for (int i = 0 ; i <= m - len; ++i) { for (int j = 0 ; j <= n - len; ++j) { if (getRec (preSum, i+1 , j+1 , i + len, j + len) <= threshold) { found = true ; }; } } if (found) { stLen = len+1 ; ans = len; } else { edLen = len-1 ; } } return ans; } int getRec (vector<vector<int >>& preSum, int i, int j, int m, int n) return preSum[m][n] - preSum[m][j-1 ] - preSum[i-1 ][n] + preSum[i-1 ][j-1 ]; } };
1124 良好表现的最长时间段 1 题目 https://leetcode-cn.com/problems/longest-well-performing-interval/
2 解题思路 较为容易想到前缀和思路：
1 对于这种良好费良好的判断，我们需要把数组转换成 -1, 1的数组
2 对上述数组作前缀和
3 那么对于每个到来的j，只需要找到最小的i，满足 preSum[j] - preSum[i] == 1即可
3.1 如何理解最小的i，也就是说，对于同一个preSum值的下标，我们总是去最小的i即可
3.2 对于 9 9 9 9 9这种全正常的思路，如何判断？ 前缀和的值本身就可以判断，大于零的下标都可以是良好工作区间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : int longestWPI (vector<int >& hours) vector<int > preSum = {0 }; for (int i = 0 ; i < hours.size (); ++i) { preSum.emplace_back ((hours[i] > 8 ? 1 : -1 ) + preSum.back ()); } int st = 0 ; int ed = 0 ; int res = INT_MIN; map<int , int > m; m[0 ] = 0 ; int lastPop = 0 ; vector<int > mono = {0 }; for (; ed < hours.size (); ++ed) { if (preSum[ed + 1 ] > 0 ) { res = std::max (res, ed + 1 ); continue ; } map<int , int >::iterator it = m.find (preSum[ed + 1 ] - 1 ); if (it != m.end ()) { res = std::max (ed - it->second, res); } if (m.find (preSum[ed + 1 ]) == m.end ()) { m[preSum[ed + 1 ]] = ed; } } return res < 0 ? 0 : res; } };