
題目解析:給定一個整數陣列與整數 k,每次可從陣列中挑選兩個總和為 k 的數字並移除,求最多能執行幾次這項操作
解題思路:先將陣列進行排序,然後設定左右兩個指標 i 和 j 分別從頭尾向中間尋找。如果相加等於 k,操作次數加一,並將兩邊指標同時往內縮;如果大於 k,代表右邊數字太大,將右指標往左移;如果小於 k,則將左指標往右移,直到兩指標交會,最後回傳操作次數。
class Solution {
public:
int maxOperations(vector<int>& nums, int k) {
int ans = 0, i = 0, j = nums.size()-1;
sort(nums.begin(), nums.end());
while(i < j){
if(nums[i] + nums[j] == k){
ans++, i++, j--;
}else if(nums[i] + nums[j] > k){
j--;
}else{
i++;
}
}
return ans;
}
};

題目解析:給定一個陣列跟整數 k,找出長度為 k 的連續子陣列,使其元素總和最大,並回傳該最大平均值
解題思路:這題屬於滑動視窗(Sliding Window)的題型。先計算前 k 個數字的總和,接著將視窗往右推,每次減去視窗最前面的數字並加上新進來的數字,比較並記錄下最大的總和,最後回傳最大總和除以 k 所得的平均值。
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int q = 0;
double ans;
for(int i=0; i<k; i++){
q += nums[i];
}
ans = q;
for(int i=k; i<nums.size(); i++){
q -= nums[i-k];
q += nums[i];
ans = max(ans, (double)q);
}
return ans / k;
}
};

題目解析:在一個字串中,找出長度為 k 的子字串,並求出該子字串中包含最多母音字母的數量(Maximum Number of Vowels in a Substring of Given Length)。
解題思路:同樣利用滑動視窗的概念。先用 set 建立一個母音集合,接著計算前 k 個字元中的母音數量。然後讓視窗開始往右滑動,每次判斷新加入的字元是否為母音以增加計數,同時判斷移出視窗的字元是否為母音以減少計數,過程中不斷更新最大值,最後回傳結果。
class Solution {
public:
int maxVowels(string s, int k) {
set<char> v{'a','e','i','o','u'};
int ans, q = 0;
for(int i=0; i<k; i++){
if(v.count(s[i])) q++;
}
ans = q;
for(int i=k; i<s.size(); i++){
if(v.count(s[i])) q++;
if(v.count(s[i-k])) q--;
ans = max(ans, q);
}
return ans;
}
};