两数之和-LeetCode

朱雀 2022-10-01 15:57 37阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例:**

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

我首先想到的也是暴力解决的办法，出现了两次问题，1.没有设置默认值，2.第二个for循环的length-1了

/**
     * @Author : Yanqiang
     * @Date : 2019/5/24
     * @Param : [nums, target]
     * @return : int[]
     * @Description : 两数之和, ---暴力运算
     */
    public static int[] twoSum1(int[] nums, int target) {
        //定义默认返回值
        int[] result = {0,0};
    
        for (int i = 0; i<nums.length; i++){
            //目标值a = 两数之和 - 当前值
            int a = target - nums[i];
            //从当前值往后循环，比如{2, 7, 11, 15};i为2，就从7开始查
            for (int k = i+1; k<nums.length; k++){
                //如果nums[k] = 目标值a,说明找到了
                if (nums[k] == a){
                    result[0] = i;
                    result[1] = k;
                }
            }
        }
        return result;
    }
    
    
    /**
     * @Author : Yanqiang
     * @Date : 2019/5/24
     * @Param : [nums, target]
     * @return : int[]
     * @Description : 两数之和, ---HashMap匹配
     */
    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            //目标值a = 两数之和 - 当前值
            int a = target - nums[i];
            //如果HashMap包含目标值 a=nums[i] ,说明找到了
            if (map.containsKey(a)) {
                return new int[] { map.get(a), i };
            }
            //如果没有重复的，HashMap存放的是Map<当前值, 当前值的数组下标>
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

public static void main(String[] args) {
        //int[] nums = {3,2,4};
        int[] nums = {2, 7, 11, 15};
        System.out.println(Arrays.toString(twoSum2(nums, 9)));
        }

转载于:https://my.oschina.net/u/3526783/blog/3053735

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/8aa2e8bb455c41cbafa89380be1cf020.png