题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路

1、暴力解法 时间O(n^2) 空间O(1);

2、利用 Hashmap 时间O(n) 空间O(n);

代码

 /**
     * 暴力枚举
     * @param nums
     * @param target
     * @return
     */
public static int[] twoSum(int[] nums, int target) {
    int s_ptr = 0, f_ptr;
    int temp;
    while (s_ptr <= nums.length - 2) {
        for (f_ptr = s_ptr + 1; f_ptr <= nums.length - 1; f_ptr++) {
            temp = nums[s_ptr] + nums[f_ptr];
            if (temp == target) {
                return new int[]{s_ptr, f_ptr};
            }
        }
        s_ptr++;
    }
    return new int[]{};
}

  /**
     * HashMap
     * @param nums
     * @param target
     * @return
     */
public static int[] twoSum_Hash(int[] nums, int target){
    HashMap<Integer, Integer> map = new HashMap<>();
    int i = 0;
    for (int n : nums){
        if (map.containsKey(target - n)){
            return new int[]{map.get(target - n),i};
        }
        map.put(n,i++);
    }
    return new int[]{};
}

LeetCode-001-两数之和