P2 求和为给定值的两个数

描述#

这个题目说的是，给你一个整数数组和一个目标值，你要找到数组里两个整数， 它们的和等于目标值。然后返回这两个整数的下标。

比如说给你的整数数组是：
1, 2, 3, 6, 8, 11
目标值是 10。那么，满足条件的两个整数是，2 和 8，它们的和是 10。所以你要返回它们的下标是 1 和 4。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public 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};
  }

  // Time: O(n), Space: O(n)
  public int[] getTwoNumSumToGivenValueHashMap(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; ++i) {
      int numNeeded = target - nums[i];
      if (map.containsKey(numNeeded)) {
        return new int[]{map.get(numNeeded), i};
      }
      map.put(nums[i], i);
    }
    return new int[]{-1, -1};
  }

}