本文目录

  1. 三数之和
  2. 矩阵置零
  3. 字母异位词分组
  4. 最长回文子串
  5. 递增的三元子序列

15. 三数之和

题目描述

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:

1
2
3
4
5
6
7
8
9
10
11
 示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:
输入:nums = []
输出:[]

示例 3:
输入:nums = [0]
输出:[]

提示:
0 <= nums.length <= 3000
$-10^5 <= nums[i] <= 10^5$

题解

排序+双指针法

这道题最直观的思路是用三重循环来暴力解。不过三重循环方法时间复杂度为$O(N^3)$,且还需要额外的去重工作。时间空间都比较复杂。因此这里不介绍这种方法。

下面采用排序+双指针的方法。

我们可以将三数之和转换为两数之和问题。即对数组中的任意一个数nums[i],确定了该数之后,剩下的工作其实就是在剩下的数中找到两数之和为-nums[i]的所有组合。因此可以转换为一个外层遍历+两数之和的问题。

其中还涉及到重复组合的问题,为了防止重复,可以首先将数组排序,使之成为有序数组。然后在循环遍历的时候,保证下层循环枚举的值大于上层循环,即对于任意三元组[a,b,c],保证有[a>b>c],这样就可以避免枚举重复值。
另外,因为要枚举出所有可能的组合,所以这里的两数之和问题需要找到所有不重复的组合项。

此外,因为数组已经有序,我们在枚举两个元素的时候,随着第一个元素的增加,第二个元素逐渐减小。这种情况下我们就可以使用双指针法。也就是说:
当我们需要枚举数组中的两个元素时,如果我们发现随着第一个元素的递增,第二个元素是递减的,那么就可以使用双指针的方法,将枚举的时间复杂度从 $O(N^2)$ 减少至 $O(N)$。

因此两数之和又可以使用标准的双指针方法来以$O(N)$的时间复杂度解决。

  • 排序:$O(NlogN)$
  • 外层遍历+两数之和:$O(N^2)$

因此总体时间复杂度可以看做是$O(N^2)$。

以辅助函数的形式来写,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
# 辅助函数:两数之和。给定数组nums,以及当前目标位置i,求[start, end]区间的两数之和等于-nums[i]的值
# nums已经有序
def twoSum(self, nums, i, start, end):
output = []
target = -nums[i]
while start<end:
if nums[start] + nums[end] == target: # 如果找到目标,则记录,并移动头尾指针,继续寻找
output.append([nums[start], nums[end], nums[i]])
end -= 1
start += 1
while start<end and nums[end]==nums[end+1] and nums[start]==nums[start-1]: # 跳过重复元素
end -= 1
start += 1
elif nums[start] + nums[end] > target: # 如果和大于target,则缩小尾指针
end -= 1
while end>start and nums[end]==nums[end+1]: # 跳过重复元素
end -= 1
else: # 如果和小于target,则前进头指针
start += 1
while start<end and nums[start]==nums[start-1]: # 跳过重复元素
start += 1
return output


def threeSum(self, nums: List[int]) -> List[List[int]]:
output = []
nums = sorted(nums, reverse=False)
for i in range(len(nums)):
if nums[i]>0: # 因为nums有序,如果当前nums[i]>0,则后面肯定都大于0,相加不可能为0。
break
if i>0 and nums[i]==nums[i-1]: # 跳过重复元素
continue
ans = self.twoSum(nums, i, i+1, len(nums)-1)
if len(ans)>0:
output.extend(ans)
return output

矩阵置零

题目描述

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

进阶:
一个直观的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗?

示例

1
2
3
4
5
6
7
8
9
10
示例1
输入:
1 1 1
1 0 1
1 1 1

输出:
1 0 1
0 0 0
1 0 1

提示:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • $-2^{31} <= matrix[i][j] <= 2^{31 - 1}$

题解

第一种方法:使用$O(MN)$的额外空间。
就是直接拷贝一份原矩阵,然后遍历原矩阵,遇到matrix[i][j]==0,就将新矩阵的ij列全置为零。

第二种方法
要记录原矩阵中0元素的位置,其实只需要一个列表即可,例如matrix[i][j]==0,则记录元组(i,j)即可。然后根据元组去设置矩阵元素。

第三种方法:使用矩阵的第一行和第一列作为标记,如果matrix[i][j]==0,则将matrix[i][0]matrix[0][j]标为0。最后遍历结束之后,将矩阵第一行为0元素的对应列全标为0,对矩阵第一列为0元素的对应的行全标为0

然后对于矩阵的第一行和第一列怎么办呢?因为第一行和第一列的值都改变过了,不知道原先是否有0元素了。因此为了解决这个问题,额外使用两个变量firstrowZerofisrtcolZero来记录矩阵的第一行和第一列是否有0元素,然后在处理完矩阵中心元素之后,再对应处理第一行和第一列即可。该方法使用的额外空间只有两个变量。

第四种方法:方法三还可以进一步优化,只用一个变量就可以解决问题。
用一个额外变量fisrtrowZero来记录第一行是否有0元素。然后第一行第一列的元素来记录第一列是否有0元素。其他不变。
这样在最后标0的时候,需要按照一定的顺序:(1)先根据第一列将对应行置零;(2)根据第一行将对应列置零,此时包含了第一列。(3)根据fisrtrowZero变量将第一行置零。

这里只给出最后第四种方法的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row, col = len(matrix), len(matrix[0])
firstrowZero = 1
# 先看第一行有没有0,记在firstrowZero变量中
for c in range(0, col):
if matrix[0][c] == 0:
firstrowZero=0
# 除第一行外,对0元素对应的行列进行标记,标在对应的第一行与第一列中
for r in range(1, row):
for c in range(0, col):
if matrix[r][c]==0:
matrix[r][0] = 0
matrix[0][c] = 0
# 先根据第一列,把对应行标为0
for r in range(1, row):
if matrix[r][0] == 0:
for k in range(col):
matrix[r][k] = 0
# 根据第一行,把对应列表为0
for c in range(0, col):
if matrix[0][c]==0:
for k in range(row):
matrix[k][c] = 0
# 根据变量判断第一行是否标0
if firstrowZero==0:
for k in range(col):
matrix[0][k] = 0

字母异位词分组

题目描述

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

说明:
所有输入均为小写字母。
不考虑答案输出的顺序。

题解

排序+哈希表

字母异位词的一个特点就是排序之后就是相同的了。因此利用这个特点,我们对每个单词进行排序,排序之后的字符串实际上就可以看做是该组的一个标识(因为具有相同标识的单词肯定属于同一组)。然后构建一个哈希表,存储{标识:[单词1, 单词2…]},最后每个标识对应一个字母异位词组。
代码如下:

1
2
3
4
5
6
7
8
9
10
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashmap = {}
for s in strs:
mark = str(sorted(s)) # 排序之后的字符串作为该组的标识
if mark not in hashmap:
hashmap[mark] = [s]
else:
hashmap[mark].append(s)
return list(hashmap.values())

最长回文子串

题目描述

给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:
输入:s = "cbbd"
输出:"bb"

示例 3:
输入:s = "a"
输出:"a"

示例 4:
输入:s = "ac"
输出:"a"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母(大写和/或小写)组成

题解

动态规划

采用动态规划求解,首先要找到递推公式。
我们使用一个二维数组dpdp[i][j]表示从字符串i到j是否是回文,即$[s_i … s_j]$是否是回文。
例如对于字符串s="aba"dp[0][1]=0表示字符串'ab',不是回文,而dp[0][2]=1表示字符串'aba'是回文。

下文中我们用s[i:j]来表示字符串s中从i到j的子串(左右都包含)。

假设s[i:j]是回文,那么如果s[i-1]==s[j+1],则s[i-1:j+1]也是回文。
反过来说,如果s[i]==s[j],那么如果s[i+1:j-1]是回文,则s[i:j]也是回文。
所以递推公式有:

1
2
if s[i]==s[j]:
dp[i][j] = dp[i+1][j-1]

边界条件:

  • 首先,s[i:i]只包含一个字符,肯定是回文,即dp[i][i] = 1
  • 其次,对于长度为2的字符串,如果s[i]==s[i+1],那么s[i:i+1]是回文,即if s[i]==s[i+1] --> dp[i][i+1]=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s)<2:
return s
elif len(s)==2:
if s[0] == s[1]:
return s
else:
return s[0]

maxlen = 1
maxpos = 0
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
# 初始化边界条件
for i in range(len(s)):
dp[i][i] = 1

# 递推子串长度,从2开始到len(s)
for i in range(2, len(s)+1):
# 枚举左边界,从0开始,到len(s)-i+1保证右边界(y=j+i-1)不超出字符串长度
for j in range(0, len(s)-i+1):
x = j # 左边界
y = j+i-1 # 右边界
if s[x]==s[y]:
# 左右边界差小于3,只可能有两种情况:
# y-x=1,即子串长度为2,(aa),肯定是回文。
# y-x=2,即子串长度为3,左右边界中间有一个值(aba),也是回文
if y-x<3:
dp[x][y] = 1
# 当子串长度大于等于3时,开始递推。
else:
dp[x][y] = dp[x+1][y-1]
# 记录最长距离和起始位置
if dp[x][y] and y-x+1>maxlen:
maxlen = y-x+1
maxpos = x
return s[maxpos: maxpos+maxlen]

两端扩展法

这个方法应该更好理解一点。

对于一个字符串s,从某一个位置s[i]开始,我们用两个指针分别判断s[i]两边是否相同,相同就继续向两端移动指针,不同则说明不是回文。这样我们对每个位置都遍历一遍,取长度最大的回文子串即可。两遍遍历,时间复杂度为$O(N^2)$。

当然上述情况是对aba这样长度为奇数的情况,但是不能找出aa这样长度为偶数的情况。
对于长度为偶数的回文,我们使用一个指针对(i,j),一开始i=0,j=1,以i,j为中心,向两端扩散,思路与上面奇数的情况相同。

对于一个字符串s,奇数情况和偶数情况都搜一遍,保留长度最长的回文子串即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n<2:
return s
output = s[0]
maxlen = 1

# 搜奇数
i = 1
while i < n:
l = i-1
r = i+1
while l>=0 and r<n:
if s[l]==s[r]:
if r-l+1>maxlen:
maxlen = r-l+1
output = s[l:r+1]
l -= 1
r += 1
else:
break
i += 1

# 搜偶数
i, j = 0, 1
while j<n:
l, r = i, j
while l>=0 and r<n:
if s[l]==s[r]:
if r-l+1>maxlen:
maxlen = r-l+1
output = s[l:r+1]
l -= 1
r += 1
else:
break
i += 1
j += 1

return output

递增的三元子序列

题目描述

给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1:
输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意

示例 2:
输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组

示例 3:
输入:nums = [2,1,5,0,4,6]
输出:true
解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示
1 <= nums.length <= $10^5$
$-2^31$ <= nums[i] <= $2^31 - 1$

题解

首先,这道题暴力搜索很简单,因为求长度为3的子序列,因此三层循环遍历就可以了。但是复杂度太高,肯定有能够优化的地方。

令s表示最小的数,m表示中间的数。
遍历数组,如果遇到比s小的数,则更新s,如果遇到比s大的数,则更新m。
这里需要注意的是,如果m存在,则证明到目前为止,已经有了以m为结尾的递增二元子序列,只需要再找到一个比m大的数即可。也就是说,m的意义可以理解为,遍历到当前位置(记为k)时,前面的序列中,最小的二元递增子序列(s与m均最小)的较大值(也就是m)的值为m。因此后续只需要再找一个比m大的数即可。

同时,之后s也是有可能被更新为更小的值的,但是这不影响m的意义。

因此,这样可以保证在找到一个三元递增序列之前,能够找到最小的二元递增序列,因此不会出现漏掉的情况。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
s = 2**31
m = 2**31
for n in nums:
if n<=s:
s = n
elif n<=m:
m = n
else:
return True
return False

同样,反着遍历也可以:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
min1 = -2**31
min2 = -2**31
for n in nums[::-1]:
if n>=min2:
min2 = n
elif n>=min1:
min1 = n
else:
return True
return False