第一題

1658.?將 x 減到 0 的最小操作數

如題上述：

? ? ? ? 本題原來的意思給定一個數字x，從數組的左邊或者右邊?使用x減去數組中的數字，直到減去最后一個數字為0時，返回最小的操作次數；如果最終減去的數組中的數字之后不能得到0，則返回-1；

? ? ? ? 我們由正難則反原理將題意轉化為如下所示：

? ? ? ? 如上圖所示，我們使用滑動窗口模型，讓窗口內的子數組之和為sum-x，左邊區域和右邊區域的數組之和為x，為了保證左右區間的數組長度最小，則中間區域的數組長度需要最長；

? ? ? ? 故此解題步驟如下所示：

步驟一：

? ? ? ? 定義左右雙指針；

步驟二：

? ? ? ? 進窗口：

? ? ? ? 右指針移動一位，并記錄sum在案；

步驟三：

? ? ? ? 判斷出窗口操作：

? ? ? ? 如果tar>sum-x，則開始出窗口操作，直到不滿足剛剛上述條件；

? ? ? ? 所謂出窗口操作則是，sum減去當前左指針所指的數值，并且左指針右移一位；

? ? ? ? 注意每一次出完窗口操作之后要更新中間數組區域的長度；

最后返回的結果是-1or整個數組長度-之前記錄的數組長度；

? ? ? ? 綜上所述，代碼如下：

class Solution {public int minOperations(int[] nums, int x) {int sum =  0;for(int a : nums){sum += a;}int tar = sum - x;if(tar < 0){return -1;}int temp = 0,res = -1;for(int left = 0,right = 0;right < nums.length;right++){temp += nums[right];while(temp > tar){temp -= nums[left++];}if(temp == tar){res = Math.max(res,right-left+1);}}if(res == -1){return res;}else{return nums.length-res;}}
}

第二題

? ? ? ? 904.?水果成籃 ?

?由上題可知：

? ? ? ? 本題的意思可以轉化為在一個最長的數組，且里面的元素種類不能超過2；

? ? ? ? 本題采用滑動模塊的思想，解題步驟如下所示：

步驟一：

? ? ? ? 定義左右雙指針；

步驟二：

? ? ? ? 進窗口操作：

? ? ? ? 右指針移動一位，將其所指的元素放在hash表里面

步驟三：

? ? ? ? 判斷操作：

? ? ? ? 當hash表的長度大于2時，hash表中左指針的元素先-1，判斷左指針所值的元素是否是否為0，如果為零，將該元素移除hash表，反之不然，同時將左指針向前移動一位；即完成出窗口操作，最后更新當前窗口的長度并記錄在案；

? ? ? ? 返回最長的窗口的長度；

? ? ? ? 代碼如下所示：

class Solution {public int totalFruit(int[] fruits) {Map<Integer,Integer> hash = new HashMap<Integer,Integer>();int res = 0;for(int left = 0,right = 0;right < fruits.length;right ++){int in = fruits[right];hash.put(in,hash.getOrDefault(in,0)+1);while(hash.size() > 2){int out = fruits[left]; hash.put(out,hash.get(out)-1);if(hash.get(out)== 0){hash.remove(out);}left ++;}res = Math.max(res,right-left+1);}return res;}
}

下面用數組代表hash表，如下所示：

class Solution {public int totalFruit(int[] fruits) {   int res = 0,n = fruits.length;int[] hash = new int[n+1];for(int left = 0,right = 0,kinds = 0;right < n;right ++){int in = fruits[right];if(hash[in] == 0){kinds++;}hash[in]++;while(kinds > 2){int out = fruits[left]; hash[out] --;if(hash[out]== 0){kinds --;}left ++;}res = Math.max(res,right-left+1);}return res;}
}

?第三題

438.?找到字符串中所有字母異位詞

題目如上所示：

? ? ? ? 首先如何能夠快速的判斷出相同的異位詞，只有采用hash表；

? ? ? ? 其次本次采用滑動窗口和hash表的方法來解決；

解題步驟如下：

步驟一：

? ? ? ? 定義所有雙指針；

步驟二：進窗口

? ? ? ? ?當前右指針所指的字符映射到hash表中的位置中，該位置上記錄的是該元素當前在窗口中的數目；每當有字符進入到窗口，其對應的hash表中的相應位置會記錄該字符的存在數量；

步驟三：

? ? ? ? 當前左右指針所指的窗口的長度是否和固定數組的長度m比較：

? ? ? ? 窗口長度大于m：

? ? ? ? ? ? ? ? 在hash表中減去當前左指針所映射位置的數量，即該元素所記錄的數量減一，同時左指針向右移動一位；

? ? ? ? 此時得到一個新的窗口，這時候要更新我們的結果，即檢查兩個hash表是否一致；

步驟四：關于兩個hash表進行比較的簡單方法：

????????

? ? ? ? 如圖所示，定義一個count變量，來記錄有效hash2表中字符的總數量，如當前hash1中需求有效字符數量為3，所以我們需要確定更新結果的前提就是hash2中所統計的count=3時，就要返回該子數組的第一個元素下標，詳細加分析如下所示：

? ? ? ? 進窗口后：如果當前該字符對應hash表中的記錄數目小于該元素的有效數目，則count變量加一；

? ? ? ? 出窗口前：如果當前該字符對應hash表中的記錄數目小于該元素的有效數目，則count變量減一；

? ? ? ? 當所記錄的count==需要的值m時，我們要更新結果：

其中代碼如下所示：

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> ret = new ArrayList<Integer> ();char[] s1 = s.toCharArray();char[] p1 = p.toCharArray();int[] hash1 = new int[26];for(char ch: p1){hash1[ch-'a']++;}int[] hash2 = new int[26];int m = p1.length;for(int left = 0,right = 0,count =0;right < s1.length;right++){char in = s1[right];hash2[in -'a']++;if(hash2[in-'a']<=hash1[in-'a']){count++;}if(right - left + 1 > m){char out = s1[left++];if(hash2[out-'a'] <= hash1[out-'a']){count--;}hash2[out-'a']--;}if(count == m){ret.add(left);}}return ret;}
}

ps：本次的內容就到這里了，如果大家感興趣的話沒救請一鍵三連哦！！！