LeetCode 001——1. 两数之和

ゝ一世哀愁。 2022-10-24 13:15 129阅读 0赞

# 题目： #

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
    你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
    你可以按任意顺序返回答案。
    
    示例 1：
    	输入：nums = [2,7,11,15], target = 9
    	输出：[0,1]
    	解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
    
    示例 2：
    	输入：nums = [3,2,4], target = 6
    	输出：[1,2]
    
    示例 3：
    	输入：nums = [3,3], target = 6
    	输出：[0,1]
     
    
    提示：
    	2 <= nums.length <= 103
    	-109 <= nums[i] <= 109
    	-109 <= target <= 109
    	只会存在一个有效答案

# 解： #

上来啥都不说，循环，  
垃圾代码如下：

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

真是牛逼，双倒数！  
![在这里插入图片描述][20210129170207776.png]

换换换，哈希表，HashMap，将值保存起来，类似于之前在AGRICH查询仓库信息时候做的缓存机制，提高速度：

public static int[] twoSum(int[] nums, int target) { 
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) { 
            if (map.containsKey(target - nums[i])) { 
                return new int[]{ i, map.get(target - nums[i])};
            } else { 
                map.put(nums[i], i);
            }
        }
        return new int[0];
    }

确实快了不少。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]

Over！

[20210129170207776.png]: /images/20221024/dd804f8029ea40fd950b17a64ada4b43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1NjUxMjc_size_16_color_FFFFFF_t_70]: /images/20221024/30481f61760a4de8881ed25de6ed824e.png