package leetcode.editor.cn;

//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 
//
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 
//
// 
//
// 示例: 
//
// 给定 nums = [2, 7, 11, 15], target = 9
//
//因为 nums[0] + nums[1] = 2 + 7 = 9
//所以返回 [0, 1]
// 
// Related Topics 数组 哈希表

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 两数之和{
	public static void main(String[] args) {
		Solution solution = new 两数之和().new Solution();
		int[] arr = {2,7,11,15};
		int target = 9;
		System.out.println(Arrays.toString(solution.twoSum(arr,target)));
		System.out.println(Arrays.toString(solution.twoSum2(arr,target)));
		System.out.println(Arrays.toString(solution.twoSum3(arr,target)));

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 * 方法一：一遍哈希表
	 * 在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。
	 * 简单点说：和减去当前遍历元素得到另一元素，判断另一元素是否在哈希表中，存在即返回；不存放将当前遍历元素，存放哈希表中。
	 * @param nums
	 * @param target
	 * @return
	 */
    public int[] twoSum(int[] nums, int target) {
		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			int temp = target - nums[i];
			if(map.containsKey(temp)){
				return new int[]{map.get(temp),i};
			}
			map.put(nums[i],i);
		}
		return null;
    }

	/**
	 * 方法二：两遍哈希表
	 * 将数组元素存放在哈希表中，再循环辨析数组，判断哈希表中是否存在元素相加等于和。
	 * @param nums
	 * @param target
	 * @return
	 */
	public int[] twoSum2(int[] nums, int target) {
		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i],i);
		}
		for (int i = 0; i < nums.length; i++) {
			int temp = target - nums[i];
			if(map.containsKey(temp) && map.containsKey(nums[i])){
				return new int[]{map.get(nums[i]),map.get(temp)};
			}
		}
		return nums;
	}

	/**
	 * 方法三：暴力解题法
	 * 遍历两次数组
	 * @param nums
	 * @param target
	 * @return
	 */
	public int[] twoSum3(int[] nums, int target) {
		for (int i = 0; i < nums.length-1; i++) {
			for (int j = i+1; j < nums.length; j++) {
				if (target == (nums[i]+nums[j])){
					return new int[]{i,j};
				}
			}
		}
		return nums;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}