LeetCode第一题：Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

英文不好，简单翻译一下，能自己翻译的跳过，看不懂我的翻译自行结合翻译网站。

给定一个整数数组，返回两个数相加等于目标值的两个数的下标值。

您可以假设每个输入都有一个解决方案，您可能不会使用相同的元素两次。

Example:

Given nums = [, , , ], target = ,

Because nums[] + nums[] =  +  = ,

return [, ].

这道题最简单的解决方法当然是双循环找到符合要求的结果。

     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 (nums[i] + nums[j] == target) {

                     return new int[]{nums[i], nums[j]};

                 }

             }

         }

         return null;

     }

首先这样写在LeetCode上可以通过，刚才试了一下，但是这个题在笔试中出现的话，应该是这个公司不想招人或者是不想通过笔试招人。

如果是在面试中出现，面试官肯定让你写出时间复杂度更低的代码，因为这个代码的时间复杂度O(n²)。下面介绍另一种解法：

public int[] twoSum(int[] nums, int target) {

        if (nums == null) {

            return null;

        }

        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {

            if (hashMap.containsKey(nums[i])) {//当map中有值需要当前值时，说明找到结果。

                return new int[]{hashMap.get(nums[i]), i};

            }

            hashMap.put(target - nums[i], i);

            //存入当前值所需要的数值，比如target为5，当前值为1，他需要4，才能得到目标值。

        }

        return null;

    }

以空间换时间HashMap底层是hash表，查找的时间复杂度为O(1)，所以上述代码的时间复杂度为O(n)，额外空间复杂度为O(n)。以空间换时间。

巴特西

LeetCode第一题：Two Sum

最新文章

热门文章