给定整数数组和一个目标数据，返回数组中的两数之和是目标数据的数组下标(给定结果要唯一)-leetcode

﹏ヽ暗。殇╰゛Y 2022-11-20 08:13 103阅读 0赞

package com.pshdhx.easy;
    
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * twoSum
     * @author pshdhx
     * 给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
     *
     */
    public class TwoSum {
    	/**
    	 * 暴力枚举法
    	 * @param nums
    	 * @param target
    	 * @return
    	 */
    	public int[] twoSum(int[] nums, int target) {
    		int res[] =new int[2];
    		for(int i=0;i<nums.length;i++) {
    			for(int j=i+1;j<nums.length;j++) {
    				if(nums[i]+nums[j]==target) {
    					res[0] = i;
    					res[1] = j;
    				}
    			}
    		}
    		return res;
        }
    	/**
    	 * 哈希法
    	 * @param nums
    	 * @param target
    	 * @return
    	 * 灵感：加法变减法=>两次循环遍历用哈希表的containsKey，数组在前，i在后；
    	 */
    	public int[] twoSum2(int[] nums, int target) {
            Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
            for (int i = 0; i < nums.length; ++i) {
                if (hashtable.containsKey(target - nums[i])) {
                	System.out.println(hashtable.get(target - nums[i])+"-----1");
                	System.out.println(i+"-----2");
                    return new int[]{hashtable.get(target - nums[i]), i};
                }
                hashtable.put(nums[i], i); // (2,0) (//进入判断了)
                System.out.println(hashtable.toString());
            }
            return new int[0];
        }
    	public static void main(String[] args) {
    		
    		  int a[]= {2, 7, 11, 15}; 
    		  int[] twoSum = new TwoSum().twoSum(a, 9); 
    		  for(int i=0;i<twoSum.length;i++) { 
    			  System.out.println(twoSum[i]);
    		  }
    		 
    		//int[] twoSum2 = new TwoSum().twoSum2(new int[] {2, 7, 11, 15}, 9);
    	}
    }

用空间换时间的做法：用哈希法减少一次遍历。