167. Two Sum II - Input array is sorted (Easy)-Two Sum
题目描述
在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。
输入输出样例
输入是一个数组（numbers）和一个给定值（target）。输出是两个数的位置，从1 开始计数。
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
在这个样例中，第一个数字（2）和第二个数字（7）的和等于给定值（9）。
题解
因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最
小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。
如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。如果两个指针指向元
素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元
素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。
可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最
优解的两个数的位置分别是l 和r。我们假设在左指针在l 左边的时候，右指针已经移动到了r；
此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达l。同理，如果我们假设
在右指针在r 右边的时候，左指针已经移动到了l；此时两个指针指向值的和大于给定值，因此
右指针会一直左移直到到达r。所以双指针在任何时候都不可能处于¹l; rº 之间，又因为不满足条
件时指针必须移动一个，所以最终一定会收敛在l 和r。
具体代码
# leetcode submit region begin(Prohibit modification and deletion)
"""
执行耗时:20 ms,击败了75.58% 的Python用户
内存消耗:13.1 MB,击败了89.31% 的Python用户
"""
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
if numbers:
start = 0
end = len(numbers) - 1
while start < end:
if numbers[start] + numbers[end] == target:
return [start + 1, end + 1]
elif numbers[start] + numbers[end] > target:
end -= 1
else:
start += 1
# leetcode submit region end(Prohibit modification and deletion)
88. Merge Sorted Array (Easy)–归并有序数组
题目描述
给定两个有序数组，把两个数组合并为一个。
输入输出样例
输入是两个数组和它们分别的长度m 和n。其中第一个数组的长度被延长至m + n，多出的
n 位被0 填补。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间。
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: nums1 = [1,2,2,3,5,6]
题解
因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即nums1 的
m 1 位和nums2 的n 1 位。每次将较大的那个数字复制到nums1 的后边，然后向前移动一位。
因为我们也要定位nums1 的末尾，所以我们还需要第三个指针，以便复制。
在以下的代码里，我们直接利用m 和n 当作两个数组的指针，再额外创立一个pos 指针，起
始位置为m+n1。每次向前移动m 或n 的时候，也要向前移动pos。这里需要注意，如果nums1
的数字已经复制完，不要忘记把nums2 的数字继续复制；如果nums2 的数字已经复制完，剩余
nums1 的数字不需要改变，因为它们已经被排好序。
具体代码
"""
执行用时：8 ms, 在所有 Python 提交中击败了99.61%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了99.49%的用户
"""
def merge(nums1, m, nums2, n):
# l为nums1的m开始索引, r为nums2的n开始索引，index为修改nums1的开始索引，然后从nums1末尾开始往前遍历
l=m-1
r=n-1
index=len(nums1)-1
# 按从大到小，从后往前修改nums1的值，每次都赋值为nums1和nums2的当前索引的较大值，然后移动索引
while l>=0 and r>=0:
# 通过nums2的值慢慢赋值给nums1
if nums1[l]>nums2[r]:
nums1[index]=nums1[l]
l-=1
else:
nums1[index]=nums2[r]
r-=1
index-=1
# 如果nums2还没遍历完
while r>=0:
nums1[index]=nums2[r]
r-=1
index-=1
return nums1
142. Linked List Cycle II (Medium)-快慢指针
题目描述
给定一个链表，如果有环路，找出环路的开始点。
输入输出样例
题解
对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。给定两个指针，
分别命名为slow 和fast，起始位置在链表的开头。每次fast 前进两步，slow 前进一步。如果fast
可以走到尽头，那么说明没有环路；如果fast 可以无限走下去，那么说明一定有环路，且一定存
在一个时刻slow 和fast 相遇。当slow 和fast 第一次相遇时，我们将fast 重新移动到链表开头，并
让slow 和fast 每次都前进一步。当slow 和fast 第二次相遇时，相遇的节点即为环路的开始点。
具体代码
"""
执行用时：32 ms, 在所有 Python 提交中击败了84.83%的用户
内存消耗：18.9 MB, 在所有 Python 提交中击败了93.97%的用户
"""
def detectCycle(head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:return None
slowp=fastp=head
while fastp and fastp.next:
slowp=slowp.next
fastp=fastp.next.next
if fastp and slowp==fastp:
slowp=head
while fastp!=slowp:
slowp=slowp.next
fastp=fastp.next
return slowp
return None
76. MinimumWindow Substring (Hard)-滑动窗口
题目描述
给定两个字符串S 和T，求S 中包含T 所有字符的最短连续子字符串的长度，同时要求时间
复杂度不得超过O(n).
输入输出样例
输入是两个字符串S 和T，输出是一个S 字符串的子串。
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
在这个样例中，S 中同时包含一个A、一个B、一个C 的最短子字符串是“BANC”。
题解
本题使用滑动窗口求解，即两个指针l 和r 都是从最左端向最右端移动，且l 的位置一定在
r 的左边或重合。注意本题虽然在for 循环里出现了一个while 循环，但是因为while 循环负责移
动l 指针，且l 只会从左到右移动一次，因此总时间复杂度仍然是O¹nº。本题使用了长度为128
的数组来映射字符，也可以用哈希表替代；其中chars 表示目前每个字符缺少的数量，flag 表示
每个字符是否在T 中存在。
具体代码
"""
执行用时：468 ms, 在所有 Python 提交中击败了5.62%的用户
内存消耗：16.1 MB, 在所有 Python 提交中击败了18.54%的用户
"""
from collections import Counter
def minWindow(s, t):
def check(dic):
return all(map(lambda x:x>=0,dic.values()))
len_t,len_s=len(t),len(s)
if len_t>len_s :return ''
if s=='' and t=='': return ''
a,b=Counter(),Counter(t)
l,mans,mins=0,float('inf'),float('-inf')
a.subtract(b)
for r in range(len(s)):
a[s[r]]+=1
while check(a):
# 说明找到更小的区间了
if mans-mins>r-l:
mins,mans=l,r
a[s[l]]-=1
l+=1
return s[mins:mans+1] if mans!=float('inf') else ''
练习-基础难度
633. Sum of Square Numbers（Easy）
Two Sum 题目的变形题之一。
题目描述
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
输入输出样例
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
题解
双指针
i 从 0 开始
j 从可取的最大数 int(math.sqrt©) 开始
total = i * i + j * j
total > c: j = j - 1，将 total 值减小
total < c: i = i + 1，将 total 值增大
total == c：返回 True
具体代码
"""
执行用时：60 ms, 在所有 Python 提交中击败了91.84%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了40.31%的用户
"""
def judgeSquareSum(c):
"""
:type c: int
:rtype: bool
"""
import math
l=0
r=int(math.sqrt(c))
while r>=l:
sums=r * r + l * l
if sums==c:
return True
elif sums>c:
r-=1
else:
l+=1
return False
680. Valid Palindrome II (Easy)
Two Sum 题目的变形题之二。
题目描述
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
输入输出样例
输入: s = “aba”
输出: true
题解
遇到第一个不同的时候，就进行判断：删左边的或删右边的
两种可能都进行下判断
c++ 没有 [::-1] 的用法，自己实现一下
时间复杂度：O(n)
空间复杂度：O(1)
具体代码
"""
执行用时：72 ms, 在所有 Python 提交中击败了82.51%的用户
内存消耗：13.6 MB, 在所有 Python 提交中击败了43.44%的用户
"""
def validPalindrome(s):
if s == s[::-1]:
return True
l, r = 0, len(s) - 1
while l < r:
if s[l] == s[r]:
l, r = l + 1, r - 1
else:
# 考虑到只能删除一个数 那么直接
a=s[l+1:r+1]
b=s[l:r]
return a==a[::-1] or b==b[::-1]
524. LongestWord in Dictionary through Deleting (Medium)
归并两个有序数组的变形题。
题目描述
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
输入输出样例
输入：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出：“apple”
题解
先根据长度和字符串进行排序，然后通过双指针处理字符串，如果字典里面的字符子串全部都在s中，则返回字符串本身，如果不存在则返回空字符串
具体代码
"""
执行用时：440 ms, 在所有 Python 提交中击败了19.25%的用户
内存消耗：15.5 MB, 在所有 Python 提交中击败了87.70%的用户
"""
def findLongestWord(s, dictionary):
"""
:type s: str
:type dictionary: List[str]
:rtype: str
"""
def check(dict, s):
# 双指针判断
ld, ls = 0, 0
while ld < len(dict) and ls < len(s):
if dict[ld] == s[ls]:
ld += 1 # 在里面就找目标里下一个数
ls += 1 # 不在里面就继续遍历原字符串
if ld == len(dict):
return True
return False
# -len(x)，表示字符串长度最长的排在前面，如果遇到了相同长度的字符串，则比较两个字符串的字典序
dictionary.sort(key=lambda x: (-len(x), x))
for dict in dictionary:
if check(dict, s):
return dict
return ''
练习-进阶难度
340. Longest Substring with At Most K Distinct Characters (Hard)
由于要VIP无法进行练习。
