每周一个小算法-twosum

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

• 思路一，暴力

#时间复杂度O(n2),双重for循环
#空间复杂度O(1)，没有使用其他变量来存储数据
#双重for循环，相加如果等于target就返回下标
public static int[] twoSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    int[] result = {i, j};
                    return result;
                }
            }
        }
        return null;
    }

• 思路二，HashMap

#时间复杂度O(n),for循环
#空间复杂度O(n)，使用了HashMap来存储
#循环遍历数组，将数组元素作为HashMap的键，将元素下标作为HashMap的值，遍历时，先求出该元素所需要的值，
例如：第一个元素是3,那么所需要的值就是6,判断HashMap是否包含6的键，若包含则返回HashMap的值和当前元素的下标
public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int j = target - nums[i];
            if (hashMap.containsKey(j)) {
                int[] result = {hashMap.get(j),i};
                return result;
            } else {
                hashMap.put(nums[i], i);
            }
        }
        return null;
    }