2.求和为给定值的两个数(AlgoCasts)

描述

这个题目说的是，给你一个整数数组和一个目标值，你要找到数组里两个整数， 它们的和等于目标值。然后返回这两个整数的下标。
例如：数组为[1, 2, 3, 6, 8, 11]，给定目标值是10，则2和8之和为10，返回下标[1,4]

注意点

• 题目十分简单，可暴力破解或借助哈希表
• 两种方法的时间复杂度和空间复杂度不同

代码引用

public class getTwoNumSumToGivenValue {
    /**
     * 暴力破解法
     * T:O(n^2) S:O(1)
     *
     * @param nums   给定数组
     * @param target 目标值
     */
    public static int[] getTwoNumSumToGivenValueBruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 哈希表
     * T:O(n) S:O(n)
     *
     * @param nums
     * @param target
     */
    public static int[] getTwoNumSumToGivenValueHashMap(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int numNeeded = target - nums[i];
            if (hashMap.containsKey(numNeeded)) {   //根据numNeeded这个key找下标value
                return new int[]{i, hashMap.get(numNeeded)};
            }
            hashMap.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 6, 8, 11};
        System.out.println(Arrays.toString(getTwoNumSumToGivenValueBruteForce(nums, 10)));
        System.out.println(Arrays.toString(getTwoNumSumToGivenValueHashMap(nums, 10)));
    }
}