两数之和

发表于

概要

这是一道常见的算法题，也是leetcode的第一道题，求一个数组中两数之和等于目标值的下标。最容易想到的就是两次暴力循环，直接处理。而最优解是配合hash循环一次就够了。

解题

  1. 暴力解法

    1
    2
    3
    4
    5
    6
    7
    8
    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 null;

  2. 一次hash循环，这种是比较难想到的，但在反正是学习算法。所以多看几次，你就学会了，以后就知道了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Map<Integer, Integer> hash = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      int num = target - nums[i];
      if (hash.containsKey(num)) {
        return new int[]{i, hash.get(num)};
      }else {
        hash.put(nums[i], i);
      }
    }
    return null;

    总结

    算法就是这样，多熟悉几次，思路就有了，多写几次，你就学会了。