LeetCode - 1

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

思路1

• 双层循环遍历数组，外层循环取first数字，内层循环取second数字，它们的和等于target则返回.

• 实现代码

  private int[] twoSum(int[] arrays, int target) {
    int length = arrays.length;
    for (int first = 0; first < length; first++) {
        for (int second = first + 1; second < length; second++) {
            if (target == arrays[first] + arrays[second]) {
                return new int[]{first, second};
            }
        }
    }
    return null;
  }
  

思路2

• 用HashMap存储key为数组中每个数字，value为该数字出现的位置。
  单层循环，每次取一个数字arrays[index]，然后判断HashMap中是否存在key = target - arrays[index]，如果存在则返回，不存在则将取到的数字放入HashMap中.

• 实现代码

  private int[] twoSum(int[] arrays, int target) {
    HashMap<Integer, Integer> map = new HashMap<>(length);
    for (int index = 0; index < arrays.length; index++) {
        if (map.containsKey(target - arrays[index])) {
            return new int[]{map.get(target - arrays[index]), index};
        }
        map.put(arrays[index], index);
    }
    return null;
  }