当前位置：首页 > article >正文

最大和值距离

article 2024/11/14 14:10:25

在这里插入图片描述

官方题解哈希

在这里插入图片描述

初始化哈希数组：
- 使用一个大小为11的数组 leftIdx 来记录每个数字第一次出现的索引，初始值为 -1。
- 数组大小为11是因为题目假设数组中的元素范围在 1 到 10 之间。
遍历数组：
- 使用一个变量 ans 来记录满足条件的最大索引差，初始值为 0。
- 从左到右遍历数组中的每个元素 nums[i]。
- 对于每个元素 nums[i]，计算其与目标和 x 的差值 k = x - nums[i]
- 检查 k 是否在 1 到 10 之间，并且 leftIdx[k] 是否不为 -1。
- 如果条件满足，计算索引差 i - leftIdx[k]，并更新 ans。
- 如果 leftIdx[nums[i]] 为 -1，则记录 nums[i] 第一次出现的索引。
返回结果：
- 返回 ans，即满足条件的最大索引差。

#include <bits/stdc++.h>
using namespace std;

/* 完成下面的函数 */
int findMaxIndexDifference(const vector<int>& nums, int n, int x) {
    vector<int> leftIdx(11, -1); // 全都初始化为-1
    int ans = 0;
    for( int i = 0; i < nums.size(); i++) {
        int k = x - nums[i];  // k是和当前元素匹配的元素
        if(k >= 1 && k <= 10 && leftIdx[k] !=-1) {
            ans = max(ans, i - leftIdx[k]); // ans是最大下标之差
        }
        if(leftIdx[nums[i]] == -1) {
            leftIdx[nums[i]] = i; // 把与nums[i]匹配的元素的
        }
    }
    return ans;
}

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int result = findMaxIndexDifference(nums, n, x);
    cout << result << endl;

    return 0;
}

例子模拟

在这里插入图片描述

直接计算并记录最大索引差

设置一个最大索引差变量
遍历数组中的所有配对。
对于每个配对，检查它们的和是否等于给定值 x。
如果等于 x，计算它们的索引差并更新最大索引差。
返回最大索引差。

#include <bits/stdc++.h>
using namespace std;

int findMaxIndexDifference(const vector<int>& nums, int n, int x) {
    int max_diff = -1; // 初始化最大索引差为-1，表示未找到配对
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] + nums[j] == x) {
                int diff = abs(i - j);
                if (diff > max_diff) {
                    max_diff = diff;
                }
            }
        }
    }
    return max_diff;
}

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int result = findMaxIndexDifference(nums, n, x);
    cout << result << endl;

    return 0;
}

时空复杂度巨大无法AC版，使用数组存放所有满足条件的索引差，然后使用STL取出最大值

（用来熟悉一下vector的STL）

遍历数组中的所有配对。
对于每个配对，检查它们的和是否等于给定值 x。
如果等于 x，计算它们的索引差并存放在数组中。
使用STL的 max_element 函数取出数组中的最大值。
返回最大值。

#include <bits/stdc++.h>
using namespace std;

int findMaxIndexDifference(const vector<int>& nums, int n, int x) {
    vector<int> index_diffs; // 用于存放满足条件的索引差
    for (int i = 0; i <= n - 2; ++i) {
        for (int j = i + 1; j <= n - 1; ++j) {
            if (nums[i] + nums[j] == x) {
                int diff = abs(i - j);
                index_diffs.push_back(diff);
            }
        }
    }
    if (index_diffs.empty()) {
        return -1; // 如果没有找到满足条件的配对，返回-1
    }
    return *max_element(index_diffs.begin(), index_diffs.end()); // 使用STL取出最大值
}

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int result = findMaxIndexDifference(nums, n, x);
    cout << result << endl;

    return 0;
}

遍历思路优化：aj从右往左，遇到即停

#include <bits/stdc++.h>
using namespace std;

/* 完成下面的函数 */
int findMaxIndexDifference(const vector<int>& nums, int n, int x) {
    int max_diff = -1; // 初始化最大索引差为-1，表示未找到配对
    for (int i = 0; i <= n - 2; ++i) {
        for (int j = n - 1; j > i; --j) { // 从右向左遍历
            if (nums[i] + nums[j] == x) {
                int diff = abs(i - j);
                if (diff > max_diff) {
                    max_diff = diff;
                }
                break; // 找到满足条件的配对后提前退出内层循环
            }
        }
    }
    return max_diff;
}

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    int result = findMaxIndexDifference(nums, n, x);
    cout << result << endl;

    return 0;
}