双数之和问题

问题描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

有点不太理解 “数组中同一个元素不能使用两遍” 具体值的什么

最简单的暴力法 时间复杂度：O(n^2) 空间复杂度: O(1)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0 ; i < nums.length ;i++ ) {
			for (int j = nums.length-1 ; j != i ; j--) {
				if ((nums[i]+nums[j]) == target) {
					System.out.print(" i:"+i+"j:"+j);
					break;
				}
			}
		}
        throw new IllegalArgumentException("No two sum solution");
    }
}

优化的思路利用哈希表

哈希表可以建立关键字key和索引的映射，通过以空间换取速度的方式，在不产生冲突时能够以恒定的时间进行快速查找，一旦产生冲突查找时间可能会从O(1) 降低到 O(n)。

时间复杂度：接近O(n) 空间复杂度：O(n)

class test{
	public int[] get(int[]num , int target){
		Map<Integer,Integer> map = new HashMap<>();
		for (int i = 0 ; i < num.length ; i++ ) {
			if (map.containsKey(target - num[i])) {
				return new int[]{map.get(target-num[i]),i}
			}
			map.put(num[i], i);
		}
	}
}