LeetCode 1. 两数之和

发表于 | 更新于 | 分类于

题意

从数组中找出两个不同的整数，使得他们的和恰好为要求得到的数。输出他们的下标。

思路

  • 想法1：最直观的思路——二重循环遍历，时间复杂度$O(n^2)$。太暴力了，考虑优化。
  • 想法2：如果序列是有序的话，可固定x然后从数组中二分查找target - x。时间复杂度$O(n*logn)$。
  • 想法3：利用桶排序的思想，存储每个数出现的次数，当遍历到x时看桶中是否存在target - x。时间复杂度$O(n)$。数据范围不知道，数组没法开，所以这个“桶”可用map实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> MP;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(MP.count(target - nums[i]))
                return {i, MP[target - nums[i]]};
            MP[nums[i]] = i;
        }
        return {-1, -1};
    }
};

总结

这是第一次使用LeetCode，所以有些生疏。

首先是要提交的代码格式，给出了Solution的大体框架，像是做填空题一般要把自己的解法填上，这是和之前刷其他OJ最明显的不同点。

其次是这道题返回的值，返回的是个二元组，一开始没反应过来该怎么写。

最后是对规范性的要求，以为给定的数据一定会满足条件，所以没加找不到时返回{-1, -1};，但这样编译也通过不了。

Donate comment here
0%