leetcode1. 两数之和

题目描述

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

必威体育苹果app下载你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

必威体育苹果app下载你可以按任意顺序返回答案。

示例

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

输出:[0,1]

解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

题目分析

简单题目,在数组中找两个数加起来等于目标数,返回这两个数在数组中的下标。也就是你要保证顺序不能变,或者说能找到原来的顺序。下面提供了两种解法以及一个思路可以自己实现一下。

解法1

必威体育苹果app下载暴力解法,直接两次遍历数组,每次判断相加是否等于目标值,等于则直接返回,时间复杂度O(n^2)。

public int[] twoSum(int[] nums, int target) {
    //1.暴力解法,直接两次遍历找
    for (int i = 0 ; i < nums.length ; i ++) {
        for (int j = 0 ; j < nums.length ; j ++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}

解法2

现在要提高效率,最容易想到的就是以空间换时间,这里用hashMap记录每个数值key以及数值的位置value,但是数组中可能存在相同的数,这时候我们该怎么处理呢?观察题目,找到两个数,那么当存在两个一样数值的数的时候,要么就是这两个数,要么只需要其中一个数另一个丢弃即可,此时我们就可以直接判断,两数之和是否等于目标值,等于直接返回,不等于丢弃后面遇到的数值,这样处理后时间复杂度为O(n)。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    for (int i = 0 ; i < nums.length ; i ++) {
        if (numMap.containsKey(nums[i])) {
            //有个数出现两次
            if (nums[i] << 1 == target) {
                return new int[]{numMap.get(nums[i]), i};
            }
            continue;
        }
        numMap.put(nums[i], i);
    }
    for (int i = 0 ; i < nums.length ; i ++) {
        int sec = target - nums[i];
        if (sec != nums[i] && numMap.containsKey(sec)) {
            return new int[]{i, numMap.get(sec)};
        }
    }
    return null;
}

其他解法

思路:必威体育苹果app下载copy一个数组进行排序,遍历数组+二分查找,最后到原数组中找到位置。

posted @ 2022-01-18 09:44  Carol淋  阅读(4)  评论(0编辑