微信公众号:路人zhang
扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 算法 > 剑指offer > 剑指offer 57-1. 和为s的两个数字
本文链接:https://www.mianshi.online/2792.html

题目描述

输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,则输出任意一对即可。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

示例 2:

输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]

限制:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

题解

(哈希表) O(n)

遍历数组,用哈希表存储每个元素以及出现次数,如果 target – nums[i] 在哈希表中存在,那么数组中和为目标值 target 的两个数就是 target – nums[i]、nums[i]。

时间复杂度

遍历一次数组的时间是 O(n) 的,哈希表的操作是 O(1) 的,所以总时间复杂度为 O(n)

空间复杂度

需要额外 O(n) 的空间用于哈希表存储 nums 中每个元素及出现次数。

C++ 代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (auto x : nums) {
            if (hash[target - x]) return {target - x, x};
            hash[x] ++ ;
        }
        return {-1, -1};
    }
};

Java 代码

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int x : nums) {
            if (hash.containsKey(target - x)) {
                return new int[]{target - x, x};
            }
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }
        return new int[]{-1, -1};
    }
}

Python 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        for x in nums:
            if target - x in hash:
                return [target - x, x]
            hash[x] = 1
        return [-1, -1]

本文由读者提供Github地址:https://github.com/tonngw


点击面试手册,获取本站面试手册PDF完整版