給定一個整數數組 nums?和一個目標值 target，請你在該數組中找出和為目標值的那?兩個?整數，并返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
```
classSolution {
? ? //暴力方法 時復O(n^2) 空復 O（1）
? ? staticfunctwoSum(_nums: [Int],_target:Int) -> [Int] {
? ? ? ? let count =? nums.count
? ? ? ? for x in 0..< count {
? ? ? ? ? ? for y in x+1 ..< count {
? ? ? ? ? ? ? ? ifnums[x] + nums[y] == target {
? ? ? ? ? ? ? ? ? ? return[x,y];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return[];
? ? }
? ? //哈希表 O(n) 空復 O(n）
? ? staticfunctwoSum1(_nums: [Int],_target:Int) -> [Int] {
? ? ? ? var hashTable : Dictionary = [:]
? ? ? ? for(index,value) in nums.enumerated() {
? ? ? ? ? ? let tag = target - value
? ? ? ? ? ? if hashTable.keys.contains(tag) {
? ? ? ? ? ? ? ? return [hashTable[tag]!,index]
? ? ? ? ? ? }
? ? ? ? ? ? hashTable.updateValue(index, forKey: value)
? ? ? ? }
? ? ? ? return[];
? ? }
}
```
給出兩個?非空 的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照?逆序?的方式存儲的，并且它們的每個節(jié)點只能存儲?一位?數字。
如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。
您可以假設除了數字 0 之外，這兩個數都不會以 0?開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
```
//時間O(max(l1,l2)) ?空間O（max(l1,l2) +1）
funcaddTwoNumbers(_l1:ListNode?,_l2:ListNode?) ->ListNode? {
? ? var root = ListNode(0)
? ? let roots = root;
? ? var ll1 = l1
? ? var ll2 = l2
? ? var carry :Int=0
? ? while(ll1?.val! = nil || ll2?.val != nil || carry ==1){
? ? ? ? let l1sumVal = ll1?.val??0
? ? ? ? let ll2sumVal = ll2?.val??0
? ? ? ? let sumVal :Int= l1sumVal + carry + ll2sumVal
? ? ? ? carry = sumVal /10
? ? ? ? let sumNode =ListNode(sumVal%10)
? ? ? ? root.next= sumNode
? ? ? ? root = sumNode
? ? ? ? ll1 = ll1?.next
? ? ? ? ll2 = ll2?.next
? ? }
? ? return roots.next
}
```
給定一個字符串，請你找出其中不含有重復字符的?最長子串?的長度。
示例?1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是?"wke"，所以其長度為 3。
?請注意，你的答案必須是 子串 的長度，"pwke"?是一個子序列，不是子串。
```
//時間O(n) ?空間O(n）
funclengthOfLongestSubstring(_s:String) ->Int{
? ? var ans = 0,start = 0,end = 0
? ? var characters = Array(s)
? ? var cache : [Character:Int] = [:]
? ? let length = s.count
? ? while start < length && end < length {
? ? ? ? let char = characters[end]
? ? ? ? if let cacheVal = cache[char] {
? ? ? ? ? ? start = max(start, cacheVal)
? ? ? ? }
? ? ? ? end += 1
? ? ? ? ans = max(ans, end - start)
? ? ? ? cache.updateValue(end, forKey: char)
? ? }
? ? return ans
}
```
給定兩個大小為 m 和 n 的有序數組?nums1 和?nums2。
請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為?O(log(m + n))。
你可以假設?nums1?和?nums2?不會同時為空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數是 (2 + 3)/2 = 2.5
```
//時間O(log(min(n,m))) ?空間O(1）
funcfindMedianSortedArrays(_nums1: [Int],_nums2: [Int]) ->Double{
? ? var m = nums1.count, n = nums2.count
? ? var a = nums1 , b = nums2
? ? if m > n {
?? ? ? ?swap(&a, &b)
? ? ? ? swap(&m, &n)
? ? }
? ? var iMin = 0, iMax = m , halflen = (m+n+1)/2
? ? while iMin <= iMax {
? ? ? ? let i = (iMin + iMax) /2
? ? ? ? let j = halflen - i
? ? ? ? if i < iMax && b[j-1] > a[i] {
? ? ? ? ? ? iMin = i +1// i is too small
? ? ? ? }
? ? ? ? else if i > iMin && a[i-1] > b[j] {
? ? ? ? ? ? iMax = i -1// i is too big
? ? ? ? }
? ? ? ? else{
? ? ? ? ? ? varmaxLeft =0
? ? ? ? ? ? ifi ==0{
? ? ? ? ? ? ? ? maxLeft = b[j-1]
? ? ? ? ? ? }
? ? ? ? ? ? else if j == 0 {
? ? ? ? ? ? ? ? maxLeft = a[i-1]
? ? ? ? ? ? }
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? maxLeft = max(a[i-1], b[j-1])
? ? ? ? ? ? }
? ? ? ? ? ? if(m + n) %2 == 1{
? ? ? ? ? ? ? ? return Double(maxLeft)
? ? ? ? ? ? }
? ? ? ? ? ? varminRight =0
? ? ? ? ? ? ifi == m {
? ? ? ? ? ? ? ? minRight = b[j]
? ? ? ? ? ? }
? ? ? ? ? ? else if j == n {
? ? ? ? ? ? ? ? minRight = a[i]
? ? ? ? ? ? }
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? minRight =min(b[j], a[i])
? ? ? ? ? ? }
? ? ? ? ? ? return Double((maxLeft + minRight)) /2.0
? ? ? ? }
? ? }
? ? return 0.0
}
```
給定一個字符串 s，找到 s 中最長的回文子串。你可以假設?s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
```
時間O(n) ?空間O（n）
funclongestPalindrome(_s:String) ->String{
? ? let strA =Array(s)
? ? if s.count == 0 {return""}
? ? let count = s.count
? ? var maxL =0///最長回文長度
? ? var cache :[Int:(Int , Int)] = [:]///最長回文對應的長度為key，開始結束下標元組為value
? ? vari =1
? ? while i < count {
? ? ? ? if maxL >=min(i*2, (count - i)*2) {///最長回文長度大于剩下可能最長回文，結束查找
? ? ? ? ? ? break
? ? ? ? }
? ? ? ? var left =0
? ? ? ? var right =0
? ? ? ? if i+1< count && strA[i] == strA[i+1]{//當前位置元素跟右邊相鄰的位置元素為中心，向兩邊擴開查找
? ? ? ? ? ? left = i
? ? ? ? ? ? right = i+1
? ? ? ? ? ? while left >=0&& right < count && strA[left] == strA[right]{
? ? ? ? ? ? ? ? if maxL < right - left{
? ? ? ? ? ? ? ? ? ? cache.removeValue(forKey: maxL)
? ? ? ? ? ? ? ? ? ? maxL = right - left
? ? ? ? ? ? ? ? ? ? cache[maxL] = (left , right)
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? left -=1
? ? ? ? ? ? ? ? right +=1
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if i-1>=0&& strA[i-1] == strA[i]{//當前位置元素跟左邊相鄰的位置元素為中心，向兩邊擴開查找
? ? ? ? ? ? if maxL >=min(i*2, (count - i)*2) {///最長回文長度大于剩下可能最長回文，結束此輪查找
? ? ? ? ? ? ? ? i +=1
? ? ? ? ? ? ? ? continue
? ? ? ? ? ? }
? ? ? ? ? ? left = i-1
? ? ? ? ? ? right = i
? ? ? ? ? ? while left >=0&& right < count && strA[left] == strA[right]{
? ? ? ? ? ? ? ? if maxL < right - left{
? ? ? ? ? ? ? ? ? ? cache.removeValue(forKey: maxL)
? ? ? ? ? ? ? ? ? ? maxL = right - left
? ? ? ? ? ? ? ? ? ? cache[maxL] = (left , right)
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? left -=1
? ? ? ? ? ? ? ? right +=1
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if i+1< count && i-1>=0&& strA[i-1] == strA[i+1] {//當前位置元素為中心，向兩邊擴開查找
? ? ? ? ? ? if maxL >=min(i*2, (count - i)*2) {///最長回文長度大于剩下可能最長回文，結束此輪查找
? ? ? ? ? ? ? ? i +=1
? ? ? ? ? ? ? ? continue
? ? ? ? ? ? }
? ? ? ? ? ? left = i-1
? ? ? ? ? ? right = i+1
? ? ? ? ? ? while left >=0&& right < count && strA[left] == strA[right]{
? ? ? ? ? ? ? ? if maxL < right - left{
? ? ? ? ? ? ? ? ? ? cache.removeValue(forKey: maxL)
? ? ? ? ? ? ? ? ? ? maxL = right - left
? ? ? ? ? ? ? ? ? ? cache[maxL] = (left , right)
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? left -=1
? ? ? ? ? ? ? ? right +=1
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? i +=1
? ? }
? ? let left = cache[maxL]?.0
? ? let right = cache[maxL]?.1
? ? let leftI = s.index(s.startIndex, offsetBy: left ??0)
? ? let rightI = s.index(s.startIndex, offsetBy: right ??0)
? ? return String(s[leftI...rightI])
}
```
