NC61 两数之和问题

今天药忘吃喽~ 2024-03-17 12:17 83阅读 0赞

### 问题描述 ###

> 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
> 
> （注：**返回**的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

### 思路分析 ###

>  *  通过 问题可将要求变相理解为，已知两个数之和（被减数）为target，求数组中的减数和差在数组中的位置。又通过注意事项可知，要将减数和差在数组中的下标位置加1（因为数组下标默认是以0开始的）
>  *  因为整型数组numbers和目标值target已知，我们可以将其看作方法的形参，从而不需要再控制台输入
>  *  可以通过遍历这个整型数组，获取到数组中的每个元素，每遍历一次，都将该元素看作是 “ 和 （被减数）- 减数 = 差” 公式中的 减数
>  *  通过 “target - numbers\[i\] = 差“ 这个公式可知，这个差一定会在数组numbers中（由题目的注意事项可得）
>  *  为了更便于理解，在遍历数组numbers时，可使用Map集合的键来存储number\[i\]，值来存储下标 i 。由此一来，便可将数组的数据和下标存储来map集合中
>  *  可以通过map的 containsKey(差值)方法，在遍历数组时，判断map中是否有这个差值，如果有，则表明满足 “ 和 （被减数）- 减数 = 差”的公式，即这个差值就是符合条件的另一个数，需要记录其下标；如果没有，继续遍历。
>  *  在找到这个差值后，除了记录其下标，还需要将下标进行升序排列。这里有多种方法，可以使用Math.min（）和Math.max（）实现，也可以将下标存在数组里，通过Array.sort()方法进行实现

### 具体代码实现 ###

// 思路： 和 （被减数）- 减数 =  差
        /*
        target 就相当于  和
        从数组中拿出的位置 i 的数 就相当于 减数
        再判断数组中是否有  和 差的值是一样的数，找到这个数后，将其下标记录下来，用于下标排序
         */
        public static int[] twoSum(int[] numbers, int target) {
            // HashMap：用于存储数组中的数字  和   它们的索引  ，即HashMap<数字，索引>，这样方便通过key找到value值，然后再判断value值
            HashMap<Integer, Integer> map = new HashMap<>();
    
            // 遍历数组
            for (int i = 0; i < numbers.length; i++) {
                // 获取数组中位置 i 的元素，也是   这个“ 和 （被减数）- 减数 =  差”的公式中的  减数
                int num = numbers[i];
                // 目标值与获取到的元素的差值
                int diff = target - num;
    
                // 检查差值是否在 HashMap 中存在
                if (map.containsKey(diff)) {
                    // 如果 这个差值在map中存在，这表明满足 “ 和 （被减数）- 减数 =  差”的公式，即这个差值就是符合条件的另一个数，需要记录其下标
                    // 在map中存储的下标是数组中的下标，其是以0开始的，为了更可读，在原有的下标上加1，让map中的下标从1开始
                    //  index1 表示   找到的 第一个数    在原始数组中的索引（从1开始）
                    int index1 = map.get(diff) + 1;
    
                    //  index2 表示   找到的 第二个数在原始数组中的索引（从1开始）
                    int index2 = i + 1;
    
                    // 下标升序排列
                    return new int[]{Math.min(index1, index2), Math.max(index1, index2)};
                }
    
                // 将当前数字与其下标存入 HashMap
                map.put(num, i);
            }
    
            // 没有找到符合条件的数字
            return new int[]{-1, -1};
        }

### 测试是否正确 ###

public static void main(String[] args) {
            int [] arr = {1,5,7,21};
            int target = 8;
            System.out.println("twoSum(arr,target) = " + Arrays.toString(twoSum(arr, target)));
        }

### 测试结果 ###

> twoSum(arr,target) = \[1, 3\]

以上就是对牛客的两数之和的个人解析，如有不妥或更好地方式，请在评论区留言