LeetCode 1 Two Sum

1年前 (2017-05-09) wang LeetCode 0评论 已收录 209℃ 浏览数:86

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 = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

开始刷题啦,这道题目其实并不难,我看到以后的第一反应是for循环。以前学过的数据结构,只是学过,应付了考试,但是我并没有将之学懂,融会贯通,并将之成为一键利器。

我发现我现在解决问题并没有第一直觉就去使用数据结构,而是使用for循环,这是一种很差的反应。我需要加深对数据结构的理解,去解决问题。

当看到他人的解决方案的时候,我是很吃惊的,没有想到别人可以把代码写的如此的娴熟,成为一件艺术品,最短的代码,清晰的逻辑,和恰到好处的数据结构,可以使问题轻松的解决。

这便是我努力的方向。

我的第一反应是for循环。

需要两层循环,第一层循环是遍历一次数组,第二层循环是在这个数后遍历整个数组,时间复杂度是O(n2)。

我一直在考虑一个问题,这里i的最大值需要不要-1,是nums.length 还是 nums.length - 1,我都运行了一遍发现结果是相同的,然后思考过后发现,两者都一样的。

如果是nums.length,那么i的最后一次循环是i = nums.length -1,然后j = i + 1; j = nums.lenth 这是j 不满足 j < muns.length的条件,会直接退出循环。

如果是nums.length - 1,那么i 的最后一次循环是 i = nums,length - 2,然后j = i + 1; j = nums.length - 1; j满足循环的条件,会进行一次判断,判断数组中最后两个数时候满足条件。而这种情况是nums.length的倒数第二种情况,说明nums.length 这种情况,最后会进行一次无用的循环,所以还是nums.length - 1是相比之下的优解。


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

    return null;
 }

这是我看完别人的代码,理解后并自己写出来的优化代码。刚开始看到很吃惊,一次循环就可以解决问题,仔细研究以后发现,用了HashMap,循环一次数组,每一次都判断Map中是否存在结果和当前值的差值的值,这点是一个核心吧我感觉,就是我写的代码是判断两个值的合是否是结果值,但是人家的思路是找结果值和当前值的插值,进行判断,如果存在这个值,则判断成功,否则将这个值存到Map,用来下一个数字的判断,这样只需要遍历一次数组,效率大增。

我觉得这是思维的问题,遇到问题,不能再像以前那样,只是为了解决问题,而是应该去用更简洁的代码,更合适的数据结构,最短的时间去解决问题。

public static int[] twoSum(int[] nums, int target) {
   int[] result = new int[2];
   Map&amp;amp;amp;amp;lt;Integer, Integer&amp;amp;amp;amp;gt; num = new HashMap&amp;amp;amp;amp;lt;Integer, Integer&amp;amp;amp;amp;gt;();
    for (int i = 0; i &amp;amp;amp;amp;lt; nums.length; i++) {
       if (num.containsKey(target - nums[i])) {
           result[1] = i;
           result[0] = num.get(target - nums[i]);
        return result;
        }

         num.put(nums[i], i);
     }

     return result;
 }
博主

Just do it. Now or never.

相关推荐

嗨、骚年、快来消灭0回复。