3112、访问消失节点的最小时间

題目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目分析

我们要在数组中找到两个数之和等于目标值，暴力的做法是遍历穷举两个数字。为了避免数量级达到$10^5$的时候超时，我需要用空间换时间，采用hash map存储已经访问过的元素的下标，进行二次匹配，这样的时间复杂度就降低到$O(n)$。

解法

1、暴力枚举

两层循环，枚举找到符合要求的数字。

public int[] twoSum(int[] nums, int target) {
    for(int i = 0;i<nums.length;++i) {
        for(int j = i+1;j<nums.length;++j) {
            if(target == nums[i]+nums[j]) {
                return new int[] {i,j};
            }
        }
    }
}

2、用Map存储已经遍历过的元素的下标，进行搜索

遍历每个元素，哈希表中查找已经有的数字，如果没有加入哈希表。

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer,Integer>();
        for (int i = 0; i < nums.length; i++) {
            int newtarget = target - nums[i];
            if(map.containsKey(newtarget)) {
                return new int[] {map.get(newtarget),i};
            }
            map.put(nums[i],i);// 之前没有匹配的数字，放入到Map中
        }
    }

如果找对应的值，可以 排序 + 二分搜索 $O(nlogn)$ $O(1)$

update 2024-05-18

由于是返回数值，所以可以先排序，遍历并二分搜索目标值。事件复杂度$O(nlogn)$

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums); // 排序
    
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1, r = nums.length - 1;
            int left = target - nums[i];
                        // 二分搜索
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] == left) {
                    return new int[] { nums[i], left };
                } else if (nums[mid] < left) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }

        return new int[] { -1, -1 };
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com