两数之和

2022-10-30 15:37:40 浏览数 (1)

题目:

思路:

      * 通过哈希map的key-value的方式来进行甄别,时间与空间复杂度都为O(N)

     * 将每次检验过的值的补数存于map中key为补数,value存数组的index坐标

     * 当新元素进入时,判断map的key中是否已经存在这个key了,如果存在,则将这个key对应的坐标拿出

     * 并且把当前数组的坐标也取出来,形成一组对应数据,本例中因为index是从1开始的,故两个数据都加上了1

代码示例:

import java.util.Arrays;

import java.util.HashMap;

import java.util.Map;

public class Solution {

    public static void main(String[] args) {

        int[] numbers = {3, 2, 4};

        int target = 6;

        int[] result = twoSum(numbers, target);

        System.out.println(Arrays.toString(result));

    }

    /**

     * 通过哈希map的key-value的方式来进行甄别,时间与空间复杂度都为O(N)

     * 将每次检验过的值的补数存于map中key为补数,value存数组的index坐标

     * 当新元素进入时,判断map的key中是否已经存在这个key了,如果存在,则将这个key对应的坐标拿出

     * 并且把当前数组的坐标也取出来,形成一组对应数据,本例中因为index是从1开始的,故两个数据都加上了1

     *

     * @param numbers int整型一维数组

     * @param target  int整型

     * @return int整型一维数组

     */

    public static int[] twoSum(int[] numbers, int target) {

        Map<Integer, Integer> map = new HashMap<>();

        int[] result = new int[2];

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

            if (map.containsKey(numbers[i])) {

                result[0] = map.get(numbers[i]) 1;

                result[1] = i 1;

            } else {

                map.put(target - numbers[i], i);

            }

        }

        return result;

    }

}

0 人点赞