leetcode第一道题，找出数组中两数之和为target的两个数，返回其下标答案及思考

约定不等于承诺〃 2022-03-02 06:17 171阅读 0赞

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpeWluZzg0MTk_size_16_color_FFFFFF_t_70]

# 初始函数 #

class Solution {
        public int[] twoSum(int[] nums, int target) {
            
        }
    }

# 思路解析 #

1.  最好想的就是暴力法，拿第一个和第二个、第三个、第四个加和是不是等于target，然后再用第二个和第三个、第四个、第五个等等依次加和，时间复杂度，很简单两个for循环，n²级别。

public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

1.  用hash表来做：首先将所有数组元素放到hash表中，然后再监测是否含有每个元素的差值？（**注意：存储数组元素为键key，因为有containsKey（）方法存取比较简单，containsValue（）比较麻烦**）

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
    }

1.  改进的思路：  
    在放入hash表的过程中，就随时监测表中是否有（target-当前值）相关元素。

class Solution {
        public int[] twoSum(int[] nums, int target) {
        	HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
        	int length = nums.length;
        	int [] result = new int[2];
        	for(int i=0;i<length;i++){
        		if(hm.containsKey(target-nums[i])) {
        			result[0] = hm.get(target-nums[i]);
        			result[1] = i;
        			break;
        		}
        		hm.put(nums[i], i);
        	}
        	return result;
        }
        
    }

思考题：

1.  hashMap取元素是怎么取的？根据key的hash值定位到table的表头，如果发现hash冲突，则根据链表来逐个比较值。只不过时间复杂度从o(1)上升到o（N）。
2.  hashMap中containsKey是怎么判断的？

public boolean containsKey(Object key) {
            return getNode(hash(key), key) != null;
        }

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpeWluZzg0MTk_size_16_color_FFFFFF_t_70]: /images/20220302/c3c9a3ba930341c29d18c453718b1b2b.png