1. 两数之和[简单] | 刷题打卡

发布于 2022年 01月 10日 20:02

腾讯服务器

88 / 年

  • 上海/北京/广州...
  • 2核 2G 4M
  • Linux/Windows
新年大优惠

腾讯服务器

425 / 年

  • 上海/北京/广州...
  • 4核 8G 10M
  • Linux/Windows
年度最便宜

腾讯服务器

1249 / 年

  • 上海/北京/广州...
  • 8核 16G 14M
  • Linux/Windows
点击查看

问题

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

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

思路一

最简单的方式是,两次循环。

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

        return new int[0];
    }
}

时间复杂度:O(n^2) 空间复杂度:O(1)

思路二

x + y = target。在确定x的情况下,相当于在数组中查找(target - x)。上面是通过遍历的方式查看是否存在y值。可以通过空间换时间的方式,提升性能。既然是找y的下标,那么可以通过将y的下标存放在map中。比较直接的写法是:

class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            Integer index = map.get(nums[i]);
            if (index == null) {
                index = 0;
            }
            map.put(nums[i], index + i);
        }

        for (int i = 0; i < nums.length; i++) {
            int next = target - nums[i];
            int index = map.get(nums[i]);
            map.put(nums[i], index - i);
            Integer nextIndex = map.get(next);
            if (nextIndex != null && nextIndex != 0) {
                return new int[] {i, nextIndex};
            }
        }

        return new int[0]; 
    }
}

上面的代码可以AC。但是leet-code的测试用例不晚上,比如nums = {3, 3, 3},target = 6,输出会是{0, 3}。不符合预期。 时间复杂度:O(n) 空间复杂度:O(n)

思路三

思路二是比较直白的从前往后找的方式。可以采用从后往前找的方式:将已遍历的元素存入map中,这样不用考虑有多个元素的情况,而且也不用考虑自身。


class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int next = target - nums[i];
            Integer index = map.get(next);
            if (index != null) {
                return new int[] {i, index};
            }
            map.put(nums[i], i);
        }
        
        return new int[0];
    }
}

硬广告

欢迎关注公众号:double6

final

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情

推荐文章