5. 523.連續的子數組和(中等,學習)

523. 連續的子數組和 - 力扣（LeetCode）

思想

1.給你一個整數數組?nums?和一個整數?k?，如果?nums?有一個?好的子數組?返回?true?，否則返回?false：
一個?好的子數組?是：

• 長度?至少為 2?，且
• 子數組元素總和為?k?的倍數。
  注意：
• 子數組?是數組中?連續?的部分。
• 如果存在一個整數?n?，令整數?x?符合?x = n * k?，則稱?x?是?k?的一個倍數。0?始終?視為?k?的一個倍數。
  2.此題條件為(s[r+1]-s[l])%k=0且r-l+1>=2,變成s[r+1]%k=s[l]%k且(r+1)-l+1>=3,所以枚舉j時，要看[0,j-3+1]是否有滿足條件的(跟[0,j-1]不一樣，不能邊枚舉邊維護次數)，這時候就map的值最好為上一次出現的下標(通法)

代碼

c++:

class Solution {
public:bool checkSubarraySum(vector<int>& nums, int k) {int n = nums.size();if (n < 2)return false;map<int, int> mp; // 和-下標mp[0] = -1;int s = 0;for (int j = 0; j < n; ++j) {s = (s + nums[j]) % k; // 都為正整數，無需變為負數if (mp.count(s)) {if (j - mp[s] + 1 >=3) // 子數組長度大于等于2，前綴和數組下標差大于等于3return true;} elsemp[s] = j;}return false;}
};

6. 面試題17.05.字母與數字(中等,重點學習)

面試題 17.05. 字母與數字 - 力扣（LeetCode）

思想

1.給定一個放有字母和數字的數組，找到最長的子數組，且包含的字母和數字的個數相同。
返回該子數組，若存在多個最長子數組，返回左端點下標值最小的子數組。若不存在這樣的數組，返回一個空數組。

代碼

c++:

class Solution {
public:vector<string> findLongestSubarray(vector<string>& array) {int n = array.size();vector<int> s(n + 1);s[0] = 0;for (int i = 0; i < n; ++i) {s[i + 1] = s[i];if (array[i][0] >= '0' && array[i][0] <= '9')++s[i + 1];else--s[i + 1];}map<int, int> mp; // 次數-左下標int begin = 0, end = 0;for (int i = 0; i <= n; ++i) { // s數組范圍:[0,n]auto it = mp.find(s[i]);if (it == mp.end()) {mp[s[i]] = i;} else if (i - it->second > end - begin) {end = i;begin = it->second;}}return {array.begin() + begin, array.begin() + end};}
};

一個變量s:

class Solution {
public:vector<string> findLongestSubarray(vector<string>& array) {int n = array.size(), begin = 0, end = 0, s = 0;unordered_map<int, int> mp;mp[s] = 0;                     // 初始前綴和為n時，位置為0for (int i = 1; i <= n; ++i) { // 從1開始遍歷if (array[i - 1][0] >= '0' && array[i - 1][0] <= '9')++s;else--s;auto it = mp.find(s);if (it == mp.end()) {// 如果沒有出現過，記錄該前綴和的第一次出現位置mp[s] = i;} else {// 如果出現過，計算當前子數組長度，更新最大子數組if (i - it->second > end - begin) {begin = it->second;end = i;}}}// 返回最大子數組return {array.begin() + begin, array.begin() + end};}
};