算法汇总

以下是所有算法汇总，包括GitHub源码地址链接：力扣算法练习汇总（持续更新…）

题目

1. 两数之和
在这里插入图片描述

题目关键点：
1、“你可以假设每种输入只会对应一个答案。”
2、“数组中同一个元素在答案里不能重复出现”
3、“任意顺序返回答案”

代码

1.借助字典表hashMap

思路

建议大家做这道题目之前，先做一下这两道：

有效的字母异位词(opens new window)
两个数组的交集(opens new window)

【245 . 有效的字母异位词 (opens new window)】这道题目是用数组作为哈希表来解决哈希问题，【349. 两个数组的交集 (opens new window)】这道题目是通过set作为哈希表来解决哈希问题。

本题呢，则要使用map作为哈希表，那么来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。

解体的关键在于：以target=9为例，nums[0] + nums[3] = 9 ； nums[3] + nums[0] =9；因为顺序无关性，所以只要和等于9即可。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
       if(nums == null || nums.length < 2){
           return new int[2];
       }
       int[] resultArr = new int[2];
       // 定义map，key = 数组中的值；value = 数组中的值的索引
       HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
       for(int i = 0 ; i < nums.length; i++){
               int temp = target - nums[i];
               // 判断map中是否存在这个key
               if(map.containsKey(temp)){
                   resultArr[0] = i;
                   resultArr[1] = map.get(temp);
                   break;
               }
               map.put(nums[i],i);
       }
       return resultArr;
    }
}

时间和空间复杂度

2.暴力法 - 双重for循环

思路

双重for循环。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
       if(nums == null || nums.length < 2){
           return new int[2];
       }
       int[] resultArr = new int[2];

       for(int i = 0 ; i < nums.length; i++){
           for(int j = i + 1; j < nums.length; j++){
               if(nums[i] + nums[j] == target){
                   resultArr[0] = i;
                   resultArr[1] = j;
                   break;
               }
           }
       }
       return resultArr;
    }
}