我們今天繼續研究陣列在演算法中的應用
167. 兩數之和 II - 輸入有序陣列
給定一個已按照升序排列 的有序陣列，找到兩個數使得它們相加之和等于目標數，
函式應該回傳這兩個下標值 index1 和 index2，其中 index1 必須小于 index2，
說明:
回傳的下標值（index1 和 index2）不是從零開始的，
你可以假設每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素，
示例:
輸入: numbers = [2, 7, 11, 15], target = 9 輸出: [1,2] 解釋: 2 與 7 之和等于目標數 9 ，因此 index1 = 1, index2 = 2 ，
我們這里直接用滑動視窗進行解題：
1.定義左指標 l為0
2.定義右指標為numbers.length - 1
3.如果左指標的值和右指標的值相加等于target直接回傳索引加1的值，否則大于時r-- 小于時l++
var twoSum = function(numbers, target) { let l = 0 let r = numbers.length - 1 while(l<r){ if(numbers[l]+numbers[r]==target){ return [l+1,r+1] } if(numbers[l]+numbers[r]>target){ r-- }else{ l++ } } return [] };
209. 長度最小的子陣列
給定一個含有 n 個正整數的陣列和一個正整數 s ，找出該陣列中滿足其和 ≥ s 的長度最小的 連續 子陣列，并回傳其長度，如果不存在符合條件的子陣列，回傳 0，
示例：
輸入：s = 7, nums = [2,3,1,2,4,3] 輸出：2 解釋：子陣列 [4,3] 是該條件下的長度最小的子陣列，
解題：
1.設定[l,r] 左閉右閉的區間內取值，r區間默認為-1就是沒有任何元素，res初始為陣列的長度加1因為我們是取最小值，陣列滿足條件的值不可能大于陣列長度加1
2.我們在l和r的區間內重復取值，當區間內的值相加滿足大于s時減掉最左邊的一個元素，sum<s時讓r++同時sum加上r的值，
3.為保證陣列不越界在r++前需要保證r+1< nums.length
4.每次有解時計算區間內的元素數量為 r - l +1 ，+1是因為索引是從0開始的，取有正確答案時的最小元素個數
5.當計算結果的長度為nums.length +1 時說明我們沒有找到正確的解直接回傳0
var minSubArrayLen = function(s, nums) { let l = 0, r = -1 // [l, r], 左閉右閉 let sum = 0 //初始化總和的值 let res = nums.length + 1 //初始化可能的最大值加1 while(l < nums.length){ if((r+ 1 <nums.length) && sum < s){ r++ sum += nums[r] } else { sum -= nums[l] l++ } if(sum >= s ){ res = Math.min(res,r-l+1) } } if(res === nums.length + 1){ return 0 } return res }
3. 無重復字符的最長子串
給定一個字串，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:
輸入: "bbbbb" 輸出: 1 解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
解題：
1.滑動視窗問題 我們在 [ans，rk]區間內取值，初始化ans為0 ，rk為-1 ，-1是為了保證滑動視窗中沒有值
2.我們創建一個set結構判斷我的的視窗中是否出現了重復的元素，當occ.has(s.charAt(rk + 1))不存在當前字符時右區間rk++，
3.rk+1時保證陣列不越界
var lengthOfLongestSubstring = function(s) { // 哈希集合，記錄每個字符是否出現過 const occ = new Set(); const n = s.length; // 右指標，初始值為 -1，相當于我們在字串的左邊界的左側，還沒有開始移動 let rk = -1, ans = 0; for (let i = 0; i < n; ++i) { if (i != 0) { // 左指標向右移動一格，移除一個字符 occ.delete(s.charAt(i - 1)); } while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) { // 不斷地移動右指標 occ.add(s.charAt(rk + 1)); ++rk; } // 第 i 到 rk 個字符是一個極長的無重復字符子串 ans = Math.max(ans, rk - i + 1); } return ans; };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/28122.html
標籤：JavaScript