微信公众号：路人zhang
网站救助计划

1.为阅读体验，本站无任何广告，也无任何盈利方法，站长一直在用爱发电，现濒临倒闭，希望有能力的同学能帮忙分担服务器成本


2.捐助10元及以上同学，可添加站长微信lurenzhang888，备注捐助，网站倒闭后可联系站长领取本站pdf内容


3.若网站能存活下来，后续将会持续更新内容

当前位置： 算法 > 剑指offer > 剑指offer 57-1. 和为s的两个数字

剑指offer 57-1. 和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字 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完整版

剑指offer