前端程式員學好演算法系列（二）數組

我們今天繼續研究數組在演算法中的應用

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;
};