leetcode1 -- Sum of two numbers

link ： leetcode01

Title Description

Topic analysis

The general idea is to use one hashmap Traversal , There is hashmap Inside , Then we are traversing the array , adopt target The difference from the current traversal element , adopt key find hashmap The number in it , But one problem with this idea is hashmap The underlying layer stores the same data , The same value is hung below , So the code will have problems when the value of the target array is the same .

This topic , I need a collection to store the elements we have traversed , Then ask this collection when traversing the array , Whether an element has been traversed , That is to say Whether it appears in this set . Then we should think of using hashing . Because the local , We not only need to know whether the element has been traversed , And know the subscript corresponding to this element , Need to use key value Structure to store ,key To store elements ,value To save the subscript , So use map The size of the right array is limited , And if the elements are small , And the hash value is too big to cause a waste of memory space .set It's a collection , There can only be one element in it key, And the problem of the sum of two numbers , Not only to judge y Whether it exists and needs to be recorded y The subscript position of , Because to return x and y The subscript . therefore set You can't use .

Code

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        int[] res = new int[2];

        if (nums == null && nums.length == 0){
    
            return res;
        }

        for (int i = 0; i < nums.length; i++) {
    
            int temp = target - nums[i];
            if (hashMap.containsKey(temp)){
    
                res[0] = hashMap.get(temp);
                res[1] = i;
            }
            hashMap.put(nums[i],i);
        }
        return res;
    }
}

Reference resources

https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF