腦圖：http://naotu.baidu.com/file/3bc98871b57aa37136f7db9c7c603376?token=7a4113ffec3d8fba

239. 滑動窗口最大值

給定一個數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字?；瑒哟翱诿看沃幌蛴乙苿右晃弧?br> 返回滑動窗口中的最大值。
進階：
你能在線性時間復雜度內解決此題嗎？
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

算法思路

• 暴力法
  兩層循環(huán)，外層循環(huán)遍歷數組，內層循環(huán)遍歷其中的窗口k個元素，找到最大值

// 偽代碼：
for i in 0..<nums.count-k+1
  max = nums[i]
  for j in i..<i+k
    max = Max(max, nums[j])
  result.appent[max]

• 雙端隊列
  利用一個單調遞減的雙端隊列，隊首保存最大值；當前值 小于 隊尾，在隊尾插入；否則，移除隊尾元素。隊列元素個數超出窗口k移除隊首。

// 偽代碼
for i in 0..<nums.count
  while !deque.isEmpty && nums[i] >= deque.last {
    deque.removeLast()   
  }
  deque.append(i)
  if  i - deque.first > k {
    deque.removeFirst()
  }
  result.append(nums[deque.first])
}

詳細題解鏈接：http://www.itdecent.cn/p/a879b0758d2c

242. 有效的字母異位詞

給定兩個字符串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。
示例 1:
輸入: s = "anagram", t = "nagaram"
輸出: true
示例 2:
輸入: s = "rat", t = "car"
輸出: false
說明:
你可以假設字符串只包含小寫字母。
進階:
如果輸入字符串包含 unicode 字符怎么辦？你能否調整你的解法來應對這種情況？
算法思路

• 排序
  異位詞排序之后相等
  對兩個異位詞進排序，之后比較排序之后的兩個字符串是否相等，相等 return true；否則 return false；

// 偽代碼
sortS = s.sorted()
sortT = t.sorted()
sortS == sortT

• 字典
  利用字典輔助存儲字母出現的次數
  key字母： value次數
  最后判斷兩個字典是否相同

// 偽代碼
for i in s {
  if sMap.keys.contains(i) {
    sMap[i] += 1
  } else {
    sMap[i] + 1  
  }
  if tMap.keys.contains(i) {
    tMap[i] += 1
  } else {
    tMap[i] + 1  
  }
  sMap == tMap
}

• 輔助數組
  利用字母表數組輔助
  字母表數組的索引為 字母的ASCII值-a的ASCII值，value為字母出現的次數
  遍歷第一個字符串，字母表數組的次數++
  遍歷第二個字符串，字母表數組的次數--
  最后查看字母表數組每個索引值是否為0

// 偽代碼
for char in s {
  alphabet[char.value - 'a'.value] += 1
}
for char in t {
  alphabet[char.value - 'a'.value] -= 1
}
for i in alphabet {
  if i != 0 {
    return false
  }
}
return true

詳細題解：http://www.itdecent.cn/p/f3fc2596edec

49. 字母異位詞分組

給定一個字符串數組，將字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字符串。
示例:
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
說明：
所有輸入均為小寫字母。
不考慮答案輸出的順序。
算法思路

• 排序、字典
  異位詞，排序之后的字符串相同即為異位詞
  利用字典，key字符串排序之后，value異位詞數組

// 偽代碼
for s in nums {
  if map.keys.contains(s.sorted()) {
    map[s.sorted].append(s)
  } else {
    map[s.sorted] = s
  }
}
return map.values

• 計數器、字典
  異位詞，每個字母出現次數相同的字符串即為異位詞
  字典，key字母表數組的字符串，value 異位詞數組

// 偽代碼
for s in nums {
  for char in s {
    alphabet[char.value - 'a'.value] += 1
  }
  if map.keys.contains(alphabet.description) {
    map[alphabet.description].append(s)
  } else {
    map[alphabet.description] = s
  }
}
return map.values

詳細題解：http://www.itdecent.cn/p/4050ac383902

1. 兩數之和

給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
算法思路

• 暴力解法
  兩次循環(huán)，判斷兩兩元素相加是否等于target

// 偽代碼
for i in 0..nums.count {
  for j in i+1..<nums.count {
    if target == nums[i] + nums[j] {
      return [i, j]
    }
  }
 }

• 雙指針
  數組排序，利用頭尾指針，計算出相加等于target的兩個元素，再遍歷原始數組，找到兩個元素的索引

// 偽代碼
sortNums = nums.sorted()
while left < right {
  if sortNums[left] + sortNums[right] == target {
    return [sortNums[left], sortNums[right]]
  } else if sortNums[left] + sortNums[right] < target {
    left += 1
  } else {
    right -= 1
  }
}
for i in 0..< nums.count {
  if nums[i] == sortNums[left] {
    result[0] = i
  }  
}
for i in 0..<nums.count {
  if nums[i] == sortNums[right] && i != result[0] {
    result[1] = i
  }
}

詳細題解：http://www.itdecent.cn/p/656e37076047

GitHub：https://github.com/huxq-coder/LeetCode
歡迎star