leetcode_两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

方法一：暴力枚举

遍历数组中的的每一个x，寻找是否存在target-x。

由于每一个位于x之前的元素都与x匹配过，因此每次遍历只需从x之后的元素开始寻找target-x。

代码：

public class Test_1_1 {

    public static void main(String[] args) {

        int nums[]=new int[]{4,7,1,9,6};

        int target=8;

        int twoSum[]= Test_1_1.twoSum(nums,target);

        //测试

        for (int i:twoSum){

            System.out.println(i);

        }

    }

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

        //定义返回的索引数组

        int twoindex[]=new int[2];

        //遍历前length-1个元素，寻找后面是否有与之匹配的元素

        for (int i=0;i<nums.length-1;i++){

            //只需从nums[i]之后寻找

            for (int j=i+1;j<nums.length;j++){

                //若匹配到则存储索引下标

                if (nums[i]+nums[j]==target){

                    twoindex[0]=i;

                    twoindex[1]=j;

                }

            }

        }

        return twoindex;

    }

}

运行结果:

方法二：哈希表查找

遍历数组中每一个x元素，先在哈希表中查找是否存在key值为target-x，如果没有，则将x作为key值，索引作为value存入哈希表中，方便后续查找；如果有，则取出相应的value值。

代码：

public class Test_1_2 {

    public static void main(String[] args) {

        int nums[]=new int[]{8,0,9,1,8,7};

        int target=10;

        int a[]=Test_1_2.twoSum(nums,target);

        //测试

        for (int i:a){

            System.out.println(i);

        }

    }

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

        int num[]=new int[2];

        //定义哈希表

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

        //遍历每一个x元素

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

            int j=target-nums[i];

            //若在map中找到与x匹配的值，则取出索引

            if (map.containsKey(j)){

                num[1]=i;

                num[0]=map.get(j);

            }

            //没有则将x作为key值存入map中

            else {

                map.put(nums[i],i );

            }

        }

        return num;

    }

}

运行结果：

巴特西

leetcode_两数之和

最新文章

热门文章