前端程序員學好算法系列（二）數組
我們今天繼續研究數組在算法中的應用
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; };
