顺序表的枚举

17.找到数组的中间位置
18.有序数组中的单一元素
19.杨辉三角II
20.超过阈值的最少操作数I
21.找出峰值
22.统计已测试设备
23.统计和小于目标的下标对数目
24.计算K置位下标对应元素的和
25.数组能形成多少数对
26.求出出现两次数字的XOR值

力扣官网： https://leetcode.cn/

---

17.找到数组的中间位置

解题思路

1. 遍历数组中的每一个下标 i。
2. 对于每个下标，分别计算其左边所有元素的和与右边所有元素的和。
3. 如果左边和等于右边和，直接返回当前下标（保证最左）。
4. 遍历结束未找到，返回 -1。

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

C++ 代码实现

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            int l = 0;
            int r = 0;
            for(int j = 0; j < i; j++){ 
                l += nums[j]; // 计算左侧元素和
            }
            for(int k = nums.size()-1; k > i; k--){
                r += nums[k]; // 计算右侧元素和
            }
            if(l == r){
                return i;
            }
        }
        return -1;
    }
};

---

18.有序数组中的单一元素

解题思路

1. 遍历数组，找到第一个与左右邻居都不相等的元素，该元素即为唯一出现一次的数。
2. 特殊情况处理：数组长度为1时，直接返回唯一元素；若首元素不等于次元素，则首元素为答案；若遍历结束未找到，说明尾元素为答案。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

C++ 代码实现

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        for(int i = 1; i < nums.size() - 1; i++){
            if(nums[i] != nums[i-1] && nums[i] != nums[i+1]){
                return nums[i];
            }
        }
        if(nums.size() == 1){
            return nums[0];
        }
        if(nums[0] != nums[1]){
            return nums[0];
        }
        return nums.back();
    }
};

---

19.杨辉三角II

解题思路

1. 杨辉三角的第 rowIndex 行有 rowIndex + 1 个元素，首尾元素均为1。
2. 中间元素的值等于上一行的左上方和正上方元素之和，即 f[i][j] = f[i-1][j-1] + f[i-1][j]。
3. 用二维数组构建杨辉三角，按规则逐行计算，最后直接返回第 rowIndex 行。

• 时间复杂度：O(n²)，n为rowIndex
• 空间复杂度：O(n²)，二维数组存储所有行

C++ 代码实现

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        int f[34][34];// 定义二维数组存储杨辉三角
        // 构建杨辉三角
        for(int i = 0; i <= rowIndex; i++){
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                	// 首尾元素为1
                    f[i][j] = 1;
                }else{
                	// 中间元素 = 上一行两元素之和
                    f[i][j] = f[i-1][j-1] + f[i-1][j];
                }
            }
        }
        // 取出第rowIndex行的结果
        vector<int> ret;
        for(int k = 0; k <= rowIndex; k++){
            ret.push_back( f[rowIndex][k] );
        }
        return ret;
    }
};

---

20.超过阈值的最少操作数I

解题思路

1. 每次操作只能删除数组中的最小元素，要让剩余元素都 ≥k，需要删除所有小于k的元素。
2. 直接遍历数组，统计小于k的元素个数，就是最少操作次数。

• 时间复杂度：O(n)，n为数组长度，仅需一次遍历
• 空间复杂度：O(1)，仅使用常数额外空间

C++ 代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int cnt = 0;
        for(int i = 0; i < nums.size(); i++){
        	// 元素小于k，需要被删除，操作次数+1
            if(nums[i] < k){
                cnt++;
            }
        }
        return cnt;
    }
};

---

21.找出峰值

1. 题目规定数组首尾元素不能是峰值，所以只需遍历数组中间元素（下标1到n-2）。
2. 对每个中间元素，判断其是否严格大于左右相邻的元素，若是则为峰值。
3. 收集所有满足条件的下标并返回。

• 时间复杂度：O(n)，n为数组长度，仅需一次遍历
• 空间复杂度：O(1)（不计返回结果的空间）

C++ 代码实现

class Solution {
public:
    vector<int> findPeaks(vector<int>& mountain) {
        vector<int> ret;
        // 遍历中间元素，跳过首尾
        for(int i = 1; i < mountain.size() - 1; i++){
       		 // 判断当前元素是否严格大于左右邻居
            if(mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1]){
                ret.push_back( i );
            }
        }
        return ret;
    }
};

---

22.统计已测试设备

解题思路

1. 按顺序遍历每个设备，若设备电量大于0，则该设备可被测试，已测试设备数+1。
2. 对当前设备之后的所有设备，若其电量大于0，则执行减1操作（不低于0）。
3. 遍历结束后，返回已测试设备的总数。

• 时间复杂度：O(n²)，n为设备数量，最坏情况下每个设备都要遍历后续所有设备
• 空间复杂度：O(1)，仅使用常数额外空间

C++ 代码实现

class Solution {
public:
    int countTestedDevices(vector<int>& batteryPercentages) {
        int ans = 0;
        for(int i = 0; i<batteryPercentages.size(); i++){
        	// 当前设备电量>0，可被测试
            if(batteryPercentages[i] > 0){
                ans++;
                // 后续所有电量>0的设备减1
                for(int j = i+1; j < batteryPercentages.size(); j++){
                    if(batteryPercentages[j] > 0){
                        batteryPercentages[j]--;
                    }
                }
            }
        }
        return ans;
    }
};

---

23.统计和小于目标的下标对数目

解题思路

1. 遍历数组中所有满足 0 <= i < j < n 的下标对。
2. 对每个下标对 (i, j)，判断 nums[i] + nums[j] 是否小于目标值 target。
3. 统计满足条件的下标对总数并返回。

• 时间复杂度：O(n²)，n为数组长度，需双重遍历所有下标对
• 空间复杂度：O(1)，仅使用常数额外空间

C++ 代码实现

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        int ans = 0;
        // 遍历所有i < j的下标对
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
            	// 判断两数之和是否小于目标值
                if(nums[i] + nums[j] < target){
                    ans++;
                }
            }
        }
        return ans;
    }
};

---

24.计算K置位下标对应元素的和

解题思路

1. 遍历数组的每个下标 i，统计其二进制表示中1的个数。
2. 若下标 i 的二进制中1的个数等于 k，则将 nums[i] 累加到结果和中。
3. 遍历结束后返回累加和。

• 时间复杂度：O(n * logn)，n为数组长度，每个下标统计1的个数需O(logn)
• 空间复杂度：O(1)，仅使用常数额外空间

C++ 代码实现

class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            int x = i;
            int cnt = 0;
            // 统计下标i的二进制中1的个数
            while(x){
                if( x & 1){
                    cnt++;
                }
                x >>= 1;
            }
            // 若1的个数等于k，累加当前元素
            if(cnt == k){
                sum += nums[i];
            }
        }
        return sum;
    }
};

---

25.数组能形成多少数对

解题思路

1. 遍历数组中的每个元素，若该元素已被配对过则跳过。
2. 从当前元素的前面的位置寻找一个未被配对且值相等的元素，找到则形成一对。
3. 标记这两个元素为已配对，配对数加1。
4. 遍历结束后，剩余元素数 = 总元素数 - 配对数×2。

• 时间复杂度：O(n²)，n为数组长度，最坏情况下需双重遍历
• 空间复杂度：O(1)，仅使用常数额外空间（标记数组可视为常量空间）

C++ 代码实现

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        int match[100] = {0}; // 定义一个标记数组
        int cnt = 0;
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                if(match[j]){
                    continue;
                }
                if(nums[i] == nums[j]){
                    match[i] = match[j] = 1;
                    cnt++;
                    break;
                }
            }
        }
        return {cnt,(int)nums.size() - 2*cnt};
    }
};

---

26.求出出现两次数字的XOR值

解题思路

1. 用 long long 类型的变量 visited 作为位标记数组，记录数字是否出现过。
2. 遍历数组中的每个数字，检查其对应位是否已被标记。
3. 若已标记，说明该数字是第二次出现，将其异或到结果 ans 中。
4. 若未标记，则将其对应位标记为已访问。
5. 遍历结束后返回结果 ans。

• 时间复杂度：O(n)，n为数组长度，仅需一次遍历
• 空间复杂度：O(1)，仅使用常数额外空间

C++ 代码实现

class Solution {
public:
    int duplicateNumbersXOR(vector<int>& nums) {
        int ans = 0;
        // 用一个long long类型的变量visited，当“位标记数组”
        long long visited = 0;
        for(int i = 0; i < nums.size(); ++i) {
            int x = nums[i];
            // 检查x对应的位是否已经被标记（即之前已经出现过）
            if(visited & ((long long)1 << x)) {
                // 已经出现过，说明这是第二次出现，异或到结果里
                ans ^= x;
            } else {
                // 第一次出现，把x对应的位标记为1
                visited |= ((long long)1 << x);
            }
        }
        return ans;
    }
};