leetcode 1.两数之和

问题描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

注意！！！只会存在一个有效答案

解题思路：

1. 暴力解法
   两层for循环查找，时间复杂度是O(n^2)。
2. 哈希表

• 哈希法是一种常用的数据结构和算法，它可以在常数时间内实现对元素的查找、插入和删除等操作，即时间复杂度是 O(1) 。当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，第一时间要想到哈希法。
• map使用 key value结构来存放数据，我们不仅要查询元素 target- nums[i] 有没有遍历过，还要返回元素对应的下标key，因此这里采用value来存下标，key来存元素。

代码示例：

1. 暴力解法

//时间复杂度O(n^2)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = nums.length;
        for(int i = 0; i < l - 1; i++) {
           for(int j = i+1; j<l; j++){
               if(nums[i] + nums[j] == target) return new int[]{i ,j};
            }
        }
     return new int[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 哈希表

//时间复杂度 O(n)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);//else可以省略
        }
        return new int[]{0, 0};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

补充与总结：

1.为什么不建议用双指针：双指针的时间复杂度为 O(nlogn)，并且双指针法要求数组有序。在这个问题中，并没有要求数组有序。因此建议使用哈希表来存储每个数值及其对应的索引。map.get(key)用于返回key值对应的value。
数组和set也不适合，数组的大小受限制，而且如果元素很少，而哈希值太大会造成内存空间的浪费。set集合只能存放一个元素，无法储存元素下标。

2.在 Java 中，Map 接口的主要实现类有几种不同类型，常用的包括 HashMap、TreeMap 和 LinkedHashMap。

• HashMap：
  HashMap 是 Java 中最常用的 Map 实现类之一。
  基于哈希表实现，提供了快速的查找、插入和删除操作。
  HashMap 不保证元素的顺序，即元素在 Map 中的存储顺序与插入顺序无关。
  允许键和值为 null，并且支持多个 null 值。
• TreeMap：
  TreeMap 是基于红黑树实现的有序 Map 类。
  TreeMap 会根据键的自然顺序或自定义比较器进行排序，并保持键的有序性。
  TreeMap 提供了一些附加的功能，如按范围查找键或值。
  与 HashMap 不同，TreeMap 是有序的，键值对是按照键的顺序排列的。
• LinkedHashMap：
  LinkedHashMap 继承自 HashMap，它在 HashMap 的基础上保持了插入顺序或访问顺序（可选）。
  在遍历时，LinkedHashMap 可以按照插入顺序或访问顺序返回键值对。
  LinkedHashMap 同样允许键和值为 null，并支持多个 null 值。