顺序表习题(中) 【力扣顺序表12题通关】C++核心代码模式详解 | 数组遍历/双指针/暴力枚举 附可直接核心代码模式(经典12题)
·
力扣顺序表12题通关
顺序表的索引
4.猜数字
5.拿硬币
6.值相等的最小索引
顺序表的大小
7.最大连续1的个数
8.差的绝对值为K的数对数目9.数组中两元素的最大乘积 (暴力枚举（双重循环）)
9.数组中两元素的最大乘积 (暴力枚举（双重循环）)
10.数组元素和与数字和的绝对差11.K个元素的最大和
12.算术三元组的数目
13.移除元素 (双指针)
顺序表的插入
14.基于排列构建数组
15.数组串联
16.拥有最多糖果的孩子
力扣官网： https://leetcode.cn/
顺序表的索引
4.猜数字
解题思路
这道题是一道非常基础的数组遍历题，核心逻辑就是：
1.遍历两个数组，按索引位置一一对比。
2.每当 guess[i] 与 answer[i] 相等时，计数器加 1。
3.因为题目限定了数组长度恒为 3，直接循环 3 次即可，无需处理其他边界情况。
- 时间复杂度：O (1)（固定循环 3 次，和输入规模无关）
- 空间复杂度：O (1)（仅使用常数额外空间）
C++ 代码实现
class Solution{
public:
int game(vector<int>& guss, vrctor<int>& answer){
int ret = 0; // 计数器
for(int i = 0; i < 3; i++){
if(guess[i] == answer[i]){
++ret;
}
}
return ret;
}
};
5.拿硬币
解题思路
这道题的核心逻辑非常直观：
1.每次最多拿 2 枚硬币，所以要拿完一堆硬币，最少次数就是 硬币数量除以2向上取整。
2.用公式表示就是：(coins[i] + 1) / 2，这是利用整数除法实现向上取整的常用技巧。
3.把每一堆硬币的最少次数相加，就是拿完所有硬币的总次数。
- 时间复杂度：O (n)，n 为硬币堆数，遍历一次数组即可
- 空间复杂度：O (1)，仅使用常数额外空间
C++ 代码实现
class Solution {
public:
int minCount(vector<int>& coins) {
int ret = 0;
for(int i = 0; i < coins.size(); i++){
ret += (coins[i] + 1) / 2;
}
return ret;
}
};
6.值相等的最小索引
解题思路
这道题是一道非常直接的线性遍历题，核心逻辑：
1.从下标 0 开始遍历数组（保证找到的第一个就是最小的下标）。
2.对每个下标 i，判断 i % 10 是否等于 nums[i]。
3.一旦找到满足条件的下标，直接返回 i（因为是顺序遍历，第一个就是最小的）。
4.遍历结束都没找到，返回 -1。
- 时间复杂度：O (n)，n 为数组长度，最坏情况遍历一次数组
- 空间复杂度：O (1)，仅使用常数额外空间
C++ 代码实现
class Solution {
public:
int smallestEqual(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++){
if(i % 10 == nums[i]){
return i;
}
}
return -1;
}
};
顺序表的大小
7.最大连续1的个数
解题思路
这是一道典型的数组遍历题，核心逻辑：
1.定义两个变量：ret 记录当前连续 1 的个数，Max 记录遇到过的最大连续 1 的个数。
2.遍历数组：
- 若当前元素为 1，则 ret++，并更新 Max = max(Max, ret)。
- 若当前元素为 0，则重置 ret = 0。
3.遍历结束后，Max 即为数组中最大连续 1 的个数。
- 时间复杂度：O (n)，n 为数组长度，仅需遍历一次数组
- 空间复杂度：O (1)，仅使用常数额外空间
C++ 代码实现
#include <vector>
using namespace std;
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
// ret：当前连续1的个数；Max：最大连续1的个数
int ret = 0;
int Max = 0;
for(int i = 0; i < nums.size(); ++i){
if(nums[i] == 1){
// 遇到1，当前连续计数+1
++ret;
// 更新最大值
if(ret > Max) Max = ret;
}else{
// 遇到0，重置当前连续计数
ret = 0;
}
}
return Max;
}
};
8.差的绝对值为K的数对数目 (暴力枚举（双重循环）)
解题思路
- 使用双重循环枚举所有满足 i < j 的数对。
- 对于每一对数字，计算它们的绝对值之差。
- 如果绝对值之差等于 k，计数器加一。
- 遍历完成后返回计数器的值。
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
C++ 代码实现
class Solution {
public:
int countKDifference(vector<int>& nums, int k) {
int ret = 0;
// 外层循环：遍历每个i
for(int i = 0; i < nums.size(); ++i){
// 内层循环：j从i+1开始，保证i < j
for(int j = i + 1; j < nums.size(); ++j){
// 计算差的绝对值是否等于k
if(abs(nums[i] - nums[j]) == k){
ret++;
}
}
}
return ret;
}
};
9.数组中两元素的最大乘积 (暴力枚举（双重循环）)
解题思路
这道题的核心是找到数组中最大的两个数，核心逻辑：
- 遍历数组，找到最大元素的下标
maxIdx。- 再次遍历数组，找到第二大元素的下标
subMaxIdx（注意排除maxIdx本身）。- 计算
(nums[maxIdx]-1) * (nums[subMaxIdx]-1)，即为所求的最大值。
- 时间复杂度：O(n)，n 为数组长度，两次遍历数组
- 空间复杂度：O(1)，仅使用常数额外空间
C++ 代码实现
class Solution {
public:
int maxProduct(vector<int>& nums) {
// 第一步：找到数组中最大元素的下标
int maxIdx = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] > nums[maxIdx]){
maxIdx = i;
}
}
// 第二步：找到数组中第二大元素的下标（不能和maxIdx相同）
int subMaxIdx = -1;
for(int i = 0; i < nums.size(); i++){
if(i != maxIdx){
if(subMaxIdx == -1 || nums[i] > nums[subMaxIdx]){
subMaxIdx = i;
}
}
}
return (nums[maxIdx] - 1) * (nums[subMaxIdx] - 1);
}
};
10.数组元素和与数字和的绝对差
解题思路
这道题的核心是分别计算数组的元素和与数字和，再求两者的绝对差，核心逻辑：
- 初始化两个变量
sum1（元素和）、sum2（数字和），初始值都为 0。- 遍历数组
nums：
- 将当前元素直接加到sum1中，完成元素和的累加。
- 用循环分解当前元素的每一位，将每一位数字加到sum2中，完成数字和的累加。- 遍历结束后，返回
abs(sum1 - sum2)，即两者的绝对差。
- 时间复杂度：O(n * d)，n 为数组长度，d 为数组中数字的平均位数
- 空间复杂度：O(1)，仅使用常数额外空间
C++ 代码实现
class Solution {
public:
int differenceOfSum(vector<int>& nums) {
int sum1 = 0, sum2 = 0;
for(int i = 0; i < nums.size(); i++){
// 累加元素和
sum1 += nums[i];
// 分解数字并累加数字和
while(nums[i]){
int temp = nums[i] % 10;
sum2 += temp;
nums[i] /= 10;
}
}
// 返回两者的绝对差
return abs(sum1 - sum2);
}
};
11.K个元素的最大和
解题思路
这道题的核心是每次都选择数组中的最大值进行操作，以最大化每次得分，核心逻辑：
- 初始化总得分
sum = 0。- 循环
k次，每次执行以下操作：
- 遍历数组，找到当前最大值m。
- 将m累加到总得分sum中。
- 将数组中该位置的值更新为m + 1（相当于执行题目中的删除并添加新元素操作）。- 循环结束后，返回总得分
sum。
- 时间复杂度：O(k * n)，k 为操作次数，n 为数组长度
- 空间复杂度：O(1)，仅使用常数额外空间
C++ 代码实现
class Solution {
public:
int maximizeSum(vector<int>& nums, int k) {
int sum = 0;
while(k--){
// 找到当前数组中的最大值
int m = -1;
for(int i = 0; i < nums.size(); i++){
if(nums[i] > m){
m = nums[i];
// 将该位置的值更新为 m+1
nums[i] = m + 1;
}
}
// 累加到总得分
sum += m;
}
return sum;
}
};
13.移除元素 (双指针)
解题思路
这道题采用双指针法，核心逻辑：
- 定义左右双指针
l和r，l从数组左端开始，r从数组右端开始。- 遍历数组：
- 若nums[l] == val，则将nums[l]与nums[r]交换，然后r--（右端指针左移，相当于移除了val）。
- 若nums[l] != val，则l++（左端指针右移，继续检查下一个元素）。- 当
l > r时循环结束，此时r+1就是数组中不等于val的元素个数。
- 时间复杂度：O(n)，n 为数组长度，只需遍历一次数组
- 空间复杂度：O(1)，仅使用常数额外空间，且在原数组上操作
C++ 代码实现
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
// 定义左右双指针
int l = 0, r = nums.size() - 1;
while(l <= r){
if(nums[l] == val){
// 交换当前元素和右端元素
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
// 右端指针左移，相当于移除了val
r--;
}else{
// 左端指针右移，继续检查下一个元素
l++;
}
}
// 不等于val的元素个数为r+1
return r+1;
}
};
顺序表的插入
14.基于排列构建数组
解题思路
这道题是一道直接的数组构造题，核心逻辑：
- 创建一个新数组
ret用于存放结果。- 遍历原数组
nums，对于每个下标i，计算nums[nums[i]]的值。- 将计算结果依次存入
ret中。- 遍历结束后，返回结果数组
ret。
- 时间复杂度：O(n)，n 为数组长度，仅需遍历一次数组
- 空间复杂度：O(n)，需要额外的数组空间存放结果
C++ 代码实现
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
vector<int> ret;
for(int i = 0; i < nums.size(); i++){
// 按题目要求计算并构建结果数组
int ans = nums[nums[i]];
ret.push_back(ans);
}
return ret;
}
};
15.数组串联
解题思路
这道题的核心是将数组自身拼接成两倍长度的新数组，核心逻辑：
- 初始化结果数组
ans，直接复制原数组nums的内容。- 遍历原数组
nums，将每个元素依次追加到ans的末尾。- 遍历结束后，返回长度为
2n的结果数组ans。
- 时间复杂度：O(n)，n 为数组长度，只需遍历一次数组
- 空间复杂度：O(n)，需要额外的
2n数组空间存放结果
C++ 代码实现
class Solution {
public:
vector<int> getConcatenation(vector<int>& nums) {
// 初始化结果数组，先复制nums
vector<int> ans = nums;
// 遍历nums，将元素追加到ans末尾
for(int i = 0; i < nums.size(); i++){
int temp = nums[i];
ans.push_back(temp);
}
return ans;
}
};
16.拥有最多糖果的孩子
解题思路
这道题的核心是先找到糖果数的最大值，再判断每个孩子加上额外糖果后是否能达到最大值，核心逻辑：
- 先遍历数组
candies，找到当前糖果数的最大值。- 再次遍历数组，对于每个孩子
i：
- 计算candies[i] + extraCandies的值。
- 若该值大于等于最大值，则结果为true，否则为false。- 遍历结束后，返回布尔数组。
- 时间复杂度：O(n)，n 为数组长度，需要两次遍历数组
- 空间复杂度：O(n)，需要额外的布尔数组空间存放结果
C++ 代码实现
class Solution {
public:
vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
vector<bool> ans;
// 找到当前糖果数的最大值
for(int i = 0; i< candies.size(); i++){
candies[i] += extraCandies;
int maxIdx = 0;
for(int j = 1; j < candies.size(); j++){
if(candies[j] >= candies[maxIdx]){
maxIdx = j;
}
}
// 遍历每个孩子，判断加上额外糖果后是否能成为最多
if(candies[i] >= candies[maxIdx]){
ans.push_back(true);
}else{
ans.push_back(false);
}
candies[i] -= extraCandies;
}
return ans;
}
};
结语
以上就是本次整理的16道顺序表入门题解，覆盖了数组遍历、双指针、暴力枚举三大基础算法模式。
这些题目虽然简单，但却是后续学习复杂数据结构和算法的重要基石。希望这份题解能帮你理清思路，掌握核心代码写法。
后续我也会持续更新更多数据结构与算法的入门题解，欢迎关注、点赞、收藏，一起进步~
更多推荐
17
0- 0
已为社区贡献5条内容
所有评论(0)