Loading...
墨滴

编程熊

2021/06/30  阅读:58  主题:橙心

【LeetCode每日一题 Day 1】 1. 两数之和

大家好,我是编程熊,今天是LeetCode每日一题的第一天,今天的你比昨天更加优秀啦!

题意

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

样例

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

题解

方法一

设两个要找的位置上的数字为 AB,则要找的就是满足 A+B=target ,因此简单的思路是,两层 for 循环遍历给的数组,第一层 for 找 A,第二层 forB,如果 AB 不是同一个位置的数且满足 A+B=target ,我们就找到了答案要找的两个位置。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
        // 找到满足条件的nums[i]+nums[j]=target
    }
}

时间复杂度:

空间复杂度:

方法二

基于方法一的前提,我们思考一下我们能不能更低的时间复杂度呢?刚刚我们固定了 A,还遍历了数组去找 B 确定是否存在 A+B=target, 那么我们能不能加快查找 B 的速度呢?

A+B=target 可以看做 B=target-A,因此可以固定 A,检查是否存在 B 满足 B=target-A。快速检索一个数据的索引,可以哈希表。此题中可以把数组中的值作为哈希表中的 key ,下标索引当 value

C++中 map 是基于红黑树,插入和查询的时间复杂度都为 unorder_map 底层基于哈希表,插入和查询时间复杂度为 。因此,选择用 unorder_map 实现。

时间复杂度:

空间复杂度:

C++代码

class Solution {
public:
    unordered_map<intint> numExist;
    vector<inttwoSum(vector<int> &nums, int target) {
      vector<int> ans;
      for (int i = 0; i < nums.size(); i++) {
        int b = target - nums[i];
        if (numExist.count(b)) {
          ans.push_back(i);
          ans.push_back(numExist.at(b));
          break;
        }
        numExist[nums[i]] = i;
      }
      return ans;
    }
};

Java代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numExist = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (numExist.containsKey(target - nums[i])) {
                return new int[]{i, numExist.get(target - nums[i])};
            }
            numExist.put(nums[i], i);
        }
        return new int[2];
    }
}

题目链接: https://leetcode-cn.com/problems/two-sum/

我是编程熊,致力于让大家都成为更好的人,欢迎 『关注』、『点赞』、『转发』支持~

编程熊

2021/06/30  阅读:58  主题:橙心

作者介绍

编程熊

公众号: 编程熊