1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。
Tags:
Categories:

题意:

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

难度:

中等

示例:

image.png

解析:

我们可以用双指针遍历两遍数组

 for(int add = 0; add < length; add++){
            for(int pair = add + 1; pair < length; pair++ ){
                if(nums[add] +nums[pair] == target){
                    int[] result = new int[]{add, pair};
                    return result;
                }
            }
}

但是复杂度达到 O(n^2), 运行时间会很长

image.png

主要耗时的步骤在查找数组上, 在第二次循环中我们重复查找了一些元素 可以把元素放入哈希表中, 减少查询复杂度

简单建个模

1.drawio.png

class Solution {

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

       //但是遍历数组的方法太麻烦, 我们换用查找复杂度为 O1 的哈希

       //哈希表存储当前索引和预期值

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

       int length = nums.length;

       for(int value = 0; value < length; value++){

        //补数, 我们根据补数来查找索引

        int completement = target - nums[value];

        //先查找是否存在, 存在就直接返回

         //匹配

         if(map.containsKey(completement)){

            int[] result = new int[]{value, map.get(completement)};

            return result;

         }

        //不存在, 放入map里面

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

    }

       return null;

    }

}