给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (mp.count(target - nums[i])) {
return {mp[target - nums[i]], i};
}
mp[nums[i]] = i;
}
return {};
}
};
|
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (auto& s : strs) {
string t = s;
sort(t.begin(), t.end());
mp[t].push_back(s);
}
vector<vector<string>> v;
for (auto& i : mp) {
v.push_back(move(i.second));
}
return v;
}
};
|
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty())
return 0;
if (nums.size() == 1)
return 1;
sort(nums.begin(), nums.end());
int ans = 1, mx = 1;
int n = nums.size();
for (int i = 1; i < n; i++) {
if (nums[i] == nums[i - 1])
continue;
if (nums[i] == nums[i - 1] + 1) {
mx++;
} else {
mx = 1;
}
ans = max(mx, ans);
}
return ans;
}
};
|
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
int pre = 0, cur = 0;
while (cur < nums.size()) {
if (nums[cur]) {
if (pre != cur)
swap(nums[pre], nums[cur]);
pre++;
}
cur++;
}
}
};
|
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明： 你不能倾斜容器。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int cur = (r - l) * min(height[l], height[r]);
int ans = cur;
while (l < r) {
ans = max(ans, cur);
if (height[l] < height[r]) {
l++;
} else {
r--;
}
cur = (r - l) * min(height[l], height[r]);
}
return ans;
}
};
|
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
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
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int i = 0;
while (i + 2 < n) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
i++;
continue;
}
int l = i + 1, r = n - 1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] < 0) {
l++;
} else if (nums[i] + nums[l] + nums[r] > 0) {
r--;
} else {
res.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
l++, r--;
}
}
i++;
}
return res;
}
};
|
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int lmx = 0, rmx = 0, mx = 0;
int ans = 0;
int l = 0, r = n - 1;
while (l < r) {
lmx = max(lmx, height[l]);
rmx = max(rmx, height[r]);
if (height[l] < height[r]) { // 低的存水上限已经定了
ans += lmx - height[l];
l++;
} else {
ans += rmx - height[r];
r--;
}
}
return ans;
}
};
|
给定一个字符串 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
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if (!n) {
return 0;
}
unordered_map<char, int> cnt;
int l = 0, r = 1;
int ans = 1;
cnt[s[0]]++;
while (r < n) {
while (r < n && cnt[s[r]] == 0) {
cnt[s[r]]++;
r++;
}
ans = max(r - l, ans);
while (l < r && cnt[s[r]] != 0) {
cnt[s[l]]--;
l++;
}
if (r < n) {
cnt[s[r]]++;
r++;
}
}
return ans;
}
};
|
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
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
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if (s.size() < p.size() || s.empty() || p.empty()) {
return {};
}
vector<int> ts(26, 0), tp(26, 0);
int n = s.size(), m = p.size();
for (int i = 0; i < m; i++) {
ts[s[i] - 'a']++, tp[p[i] - 'a']++;
}
int mc = 0;
for (int i = 0; i < 26; i++) {
mc += tp[i] == ts[i];
}
int l = 0, r = m;
vector<int> pos;
while (r <= n) {
if (mc == 26) {
pos.push_back(l);
}
if (r == n)
break;
mc -= tp[s[l] - 'a'] == ts[s[l] - 'a'];
mc -= tp[s[r] - 'a'] == ts[s[r] - 'a'];
ts[s[l] - 'a']--, ts[s[r] - 'a']++;
mc += tp[s[l] - 'a'] == ts[s[l] - 'a'];
mc += tp[s[r] - 'a'] == ts[s[r] - 'a'];
l++, r++;
}
return pos;
}
};
|
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> pre(n + 1, 0);
unordered_map<int, int> mp;
int ans = 0;
mp[0] = 1;
for (int i = 0; i < n; i++) {
pre[i + 1] = pre[i] + nums[i];
ans += mp[pre[i + 1] - k];
mp[pre[i + 1]]++;
}
return ans;
}
};
|
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| vector<int> maxSlidingWindow(vector<int> &nums, int k) {
deque<int> q;
int n = nums.size();
for (int i = 0; i < k; i++) {
while (!q.empty() && nums[q.back()] < nums[i]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; i++) {
while (!q.empty() && q.front() <= i - k) {
q.pop_front();
}
while (!q.empty() && nums[q.back()] < nums[i]) {
q.pop_back();
}
q.push_back(i);
ans.push_back(nums[q.front()]);
}
return ans;
}
|
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| class Solution {
public:
string minWindow(string s, string t) {
int n = s.size(), m = t.size();
if (n < m) {
return "";
}
vector<int> mc(128, 0), cur(128, 0);
for (int i = 0; i < m; i++) {
mc[t[i]]++, cur[s[i]]++;
}
int tot = 0;
for (char c = 'A'; c <= 'Z'; c++) {
if (mc[c] <= cur[c]) {
tot++;
}
}
for (char c = 'a'; c <= 'z'; c++) {
if (mc[c] <= cur[c]) {
tot++;
}
}
int L = 0, R = 0;
string ans = "";
int l = 0, r = m;
if (tot == 52) {
if (R == 0 || r - l < R - L) {
L = l, R = r;
}
}
while (r < n) {
while (tot != 52 && r < n) {
tot -= cur[s[r]] >= mc[s[r]];
cur[s[r]]++;
tot += cur[s[r]] >= mc[s[r]];
r++;
}
while (l < r && mc[s[l]] < cur[s[l]]) {
tot -= cur[s[l]] >= mc[s[l]];
cur[s[l]]--;
tot += cur[s[l]] >= mc[s[l]];
l++;
}
if (tot == 52) {
if (R == 0 || r - l < R - L) {
L = l, R = r;
}
}
tot -= cur[s[l]] >= mc[s[l]];
cur[s[l]]--;
tot += cur[s[l]] >= mc[s[l]];
l++;
while (l < r && mc[s[l]] == 0) {
tot -= cur[s[l]] >= mc[s[l]];
cur[s[l]]--;
tot += cur[s[l]] >= mc[s[l]];
l++;
}
}
return s.substr(L, R - L);
}
};
|
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0;
int mx = nums.front();
for (int i : nums) {
pre = max(pre + i, i);
mx = max(mx, pre);
}
return mx;
}
};
|
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> v;
int l = -1, r = -1;
for (auto& a : intervals) {
if (l == -1) {
l = a[0], r = a[1];
continue;
}
if (a[0] > r) {
v.push_back({l, r});
l = a[0];
}
r = max(r, a[1]);
}
v.push_back({l, r});
return v;
}
};
|
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
|
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法， 且在 O(n) 时间复杂度内完成此题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> pre(n, 1), suf(n, 1);
pre[0] = nums[0], suf[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] * nums[i];
suf[n - i - 1] = suf[n - i] * nums[n - i - 1];
}
vector<int> arr;
for (int i = 0; i < n; i++) {
if (i - 1 >= 0 && i + 1 <= n - 1)
arr.push_back(pre[i - 1] * suf[i + 1]);
else if (i == 0)
arr.push_back(suf[1]);
else
arr.push_back(pre[n - 2]);
}
return arr;
}
};
|
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] <= 0)
continue;
while (nums[i] <= n && nums[i] - 1 >= 0 &&
nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1)
return i + 1;
}
return n + 1;
}
};
|
给定一个 $m \times n$ 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
if (!n)
return;
int m = matrix[0].size();
vector<bool> row(n), col(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
row[i] = col[j] = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (row[i] || col[j])
matrix[i][j] = 0;
}
}
}
};
|
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
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
| class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int n = matrix.size();
if (!n)
return {};
if (n == 1)
return matrix[0];
int m = matrix[0].size();
if (m == 1) {
vector<int> v;
for (int i = 0; i < n; i++)
v.emplace_back(matrix[i][0]);
return v;
}
int x = 0, y = 0, k = 0;
vector<pair<int, int>> dxy = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<int> v = {matrix[x][y]};
matrix[x][y] = -101;
while (v.size() < n * m) {
int px = x + dxy[k].first, py = y + dxy[k].second;
if (px < 0 || px >= n || py < 0 || py >= m ||
matrix[px][py] == -101) {
k = (k + 1) % 4;
px = x + dxy[k].first, py = y + dxy[k].second;
}
v.push_back(matrix[px][py]);
matrix[px][py] = -101;
x = px, y = py;
}
return v;
}
};
|
给定一个 $n\times n$ 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
