问题

给定一个整数数组 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 春招闯关活动」, 点击查看 活动详情