LeetCode01.两数之和

mingyuer / 2024-03-16 / 原文

ques:

给定一个整数数组 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]

ans:

暴力直接遍历，没有什么其他好方法，除非采用hash表，不过这里要注意例三的情况，就是第二层遍历要从该元素末尾往后接着遍历，而不能从头开始（所以我那个迭代器+find+distance还不知道怎么解决）

还有就是，不需要定义vector <int> twoNum;在官方题解中直接放回形式采用return {i,j};即可。

值得注意的是，我多次提交都显示编译错误，因为我只在双层循环内部写了return语句，而在循环之外，应该写上return {};方为正解。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


class Solution {
private:
    vector<int> twoNum;

public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int subtraction;
        for (int i = 0; i < nums.size(); i++) {

            subtraction = target - nums[i];
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[j] == subtraction) {
                    twoNum.push_back(i);
                    twoNum.push_back(j);

                } else
                    continue;
            }
        }
        return twoNum;
    }
};


/* class Solution {
private:
    vector<int> twoNum;

public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int subtraction;
        for (int i = 0; i < nums.size();i++)
        {
            if(nums[i]>target)
                continue;
            else
            {
                vector<int>::iterator it;//定义迭代器变量，以指向查找值，最后通过距离转换为下标值
                subtraction = target - nums[i];
                if((it=find(nums.begin(),nums.end(),subtraction))!=nums.end())//find函数返回值为迭代器，返回vector.end()代表没找到，vector最后一个元素为vector.end()-1
                {
                    twoNum.push_back(i);
                    twoNum.push_back(distance(nums.begin(), it));
                    return twoNum;
                }

            }
        }
    }   
};
 */

/* class Solution {
private:
    vector<int> smallnum;
    vector<int> bignum;
    int middletag;//作为target的二分值，小的放入smallnum，大的放入bignum

public:
    vector<int> twoSum(vector<int>& nums, int target) {
        middletag = target / 2;
        for (int i = 0; i < nums.size();i++)
        {
            if(nums[i]>target)
                continue;
            else if(nums[i]<=middletag)
                smallnum.push_back(nums[i]);
            else
                bignum.push_back(nums[i]);
        }
        for (int i = 0; i < smallnum.size();i++)
        {
            int subtraction = target - smallnum[i];

        }
    }
}; */

summary：

想了两种方法也没想出能让时间复杂度小于O(N²)的，最开始闪过一下哈希表但是不会用，也没往这方面想了，尝试了二分法也没用，尝试调用STL库的find函数还有distance函数也用的不是很明白，主要是也没有降低时间开销，不过还是学到了一些知识，比如定义迭代器变量以及学了判断结束的方法find(nums.begin(),nums.end(),subtraction)!=nums.end()

现在先暂时采用暴力遍历解决，晚些时候学学哈希表的使用^_^

贴上官方题解~

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。