给定一个整数数组 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[];
}
}
```
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 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])
}
```
