leetcode--1--两数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode--1--两数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

暴力枚举法

代码如下：

# include <iostream>

int* twoSum(int*nums, int target) {
    int Array[2]; // 定义一个长度为2的数组，用于存放结果
    for (int i = 0; i < 5; i++) {
        for (int j = i + 1; j < 5; j++) {
            if (nums[i] + nums[j] == target) {
                Array[0] = i + 1; // 加1的原因：数组的下标索引是从0开始，元素的位置从1开始
                Array[1] = j + 1;
                return Array; // 返回结果数组的首地址
            }
        }     
    }
}


int main() {
    int numbers[5] = { 10, 20, 30, 40, 50 }; // 创建一个整型数组，包含5个元素
    int *result = twoSum(numbers, 60); // 调用函数
    std::cout << '[' << result[0] << ',' << result[1] << ']' << std::endl; // 输出结果
    return 0;
}

1. 时间复杂度分析
外层循环从索引0遍历到n-1，其中n是数组的长度，因此有n次迭代。
内层循环从索引i+1遍历到n-1，最坏情况下需要n-1次迭代。
在内层循环中进行了常数时间的加法操作和比较操作。
因此，暴力求解法总体的时间复杂度为O(n^2)，其中n是数组的长度。

2. 空间复杂度分析
除了存储输入数组和输出结果的空间外，该算法没有使用额外的空间。
输入数组的空间复杂度为O(n)。
输出结果是一个长度为 2 的整型数组 Array，用于存放结果。因此，不随输入大小变化，空间复杂度为 O(1)，即常数级别的额外空间消耗。
因此，暴力求解法总体的空间复杂度为O(n)。

尽管该方法时间复杂度较高，但对于小规模的问题或输入规模不大的情况下，仍然可以使用。但对于大规模的问题或输入规模较大的情况下，该方法的效率会较低，因此需要考虑使用其他更优化的方法来解决该问题，如哈希表等，来优化时间复杂度。

部分引用自：https://blog.csdn.net/AAADiao/article/details/131426269

后续持续改进！！！ 文章来源地址https://www.toymoban.com/news/detail-858006.html

到了这里，关于leetcode--1--两数之和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！