flower-rain/docs/石亚玲/syl.md

两数之和

给定一个整数数组nums和一个整数目标值target。在该数组中找处和为目标值target的两个整数，并返回它们的数组下标。

题解

    public class Solution{
        public int[] GetTwoNums(int[] nums , int target){
            Map<integer,integer>map = new HashMap<integer,integer>();
            for(int i = 0; i < nums.length ; i++){
                if(map.containskey(target - nums[i])){
                    return new int[]{map.get(target - nums[i]),i};
                }
                map.put(nums[i],i);
            }
            return new int[0];
        }
    }

解释

Map

• Map是Java中的键值对集合 ;
• 存储的是[key -> value]的映射关系 ;

map.containskey()

• 判断map中是否存在target - nums[i];

map.put()

• 存入map，nums[i]作为key，i作为value;

map.get()

• 根据传入的key，从HashMap中获取对应的value;

---

评价

为什么用 Map 接口而不是直接 HashMap 定义？

• Map是Java集合框架中接口，定义了“键值对存储”的统一规范：put、get、containskey等方法。HashMap是Map接口的具体实现类。
• 用Map声明变量，是因为此代码只需依赖“键值对存储”的抽象能力，不绑定HashMap。
• 如果直接用HashMap声明，未来切换实现时，需要修改所有需要用到map的地方，维护成本极高。
• 哈希表能够实现O(1)快速查找。

时间和空间复杂度比较

• 暴力查找，时间：O(n²) 空间O(1)：
• 哈希查找，时间：O(n) 空间：O(n)

---