三数之和
给你一个包罗 n 个整数的数组 nums,判定 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出全部和为 0 且不重复的三元组。
注意:答案中不可以包罗重复的三元组。
class Solution { func threeSum(_ nums: [Int]) -> [[Int]] { var ans = [[Int]]() if nums.count < 3 { return ans } let nums = nums.sorted() // 排序,对有序数组才有效 for i in 0 ... nums.count - 3 { // 由于是从小到大有序数组,以是这个数大于0,后面的数都比他大因此肯定和大于0且直接break跳出循环 if nums > 0 { break } // 去重,如果与前一个数雷同,则直接跳过这一次不须要处理惩罚 if i > 0 && nums == nums[i-1] { continue } var left = i + 1, right = nums.count - 1// 界说左右指针 //开始左右夹逼,如果三数之和小于0,则left往右移1,大于0则right往左移1 while left < right { let result = nums + nums[left] + nums[right] if result == 0 { ans.append([nums, nums[left], nums[right]]) //跳过第二第三个数雷同的效果 repeat { left += 1 } while left < right && nums[left] == nums[left - 1] repeat { right -= 1 } while left < right && nums[right] == nums[right + 1] } else if result < 0 { //跳过第二个数雷同的效果 repeat { left += 1 } while left < right && nums[left] == nums[left - 1] } else { //跳过第三个数雷同的效果 repeat { right -= 1 } while left < right && nums[right] == nums[right + 1] } } } return ans }}此题须要注意的是两点
链表的中央结点
题目:给定一个头结点为 head 的非空单链表,返回链表的中央结点。
如果有两个中央结点,则返回第二个中央结点。
class Solution { func middleNode(_ head: ListNode?) -> ListNode? { if head?.next == nil { return head } var slow = head var fast = head while fast?.next != nil { slow = slow?.next fast = fast?.next?.next } return slow }}此题利用快慢指针,慢的取next,快的取next.next,快指针取完的时间慢指针会停顿在中央节点。
找到字符串中全部字母异位词
给定两个字符串 s 和 p,找到 s 中全部 p 的 异位词 的子串,返回这些子串的起始索引。不思量答案输出的次序。
异位词 指由雷同字母重分列形成的字符串(包罗雷同的字符串)。
class Solution { func findAnagrams(_ s: String, _ p: String) -> [Int] { let arrS = Array(s), arrP = Array(p) var need = [Character: Int](), window = [Character: Int]() for c in arrP { need[c, default: 0] += 1 } var left = 0, right = 0 var valid = 0 var ans = [Int]() while right < arrS.count { let c = arrS[right] right += 1 // 举行窗口内数据的一系列更新 if need.keys.contains(c) { window[c, default: 0] += 1 if window[c] == need[c] { valid += 1 } } // 判定左侧窗口是否要紧缩 while right - left >= arrP.count { // 当窗口符合条件时,把起始索引参加 ans if valid == need.count { ans.append(left) } let d = arrS[left] left += 1 if need.keys.contains(d) { if window[d] == need[d] { valid -= 1 } window[d, default: 1] -= 1 } } } return ans }}滑动窗口有模板,碰到雷同题目都可套用模板。