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)}