【算法刷题】第一篇——哈希

个人简介： 

> 📦个人主页：赵四司机
> 🏆学习方向：JAVA后端开发 
> 📣种一棵树最好的时间是十年前，其次是现在！
> 🔔博主推荐网站：牛客网  刷题|面试|找工作神器
> 💖喜欢的话麻烦点点关注喔，你们的支持是我的最大动力。

前言：

最近有不少小伙伴私信博主问我马上到秋招了，而自己平时没怎么练过算法，在算法这一块存在很大的弱势，应该怎么快速提升自己的算法水平。在这里我首先要说的是算法能力并不是可以快速掌握的，这需要慢慢积累，因为算法不仅考验我们的知识记忆深度，还考验我们的思维广度，因此很多很多大厂面试都会注重算法的考核。

其实博主一开始也没怎么练过算法题，但是对于中等简单的算法题还是可以通过一段时间的刷题来习得的。我最近就在一个叫牛客网的网站上面刷面试算法题，上面还很贴心给我们总结出了常考的题目，像剑指Offer、面试必刷Top101、面试高频榜单都有，先上图为证：

 怎样，是不是很心动，下面我给你们介绍一下这个网站，传送门：牛客刷题神器

目录

一：两数之和

1.题目要求

2.解题思路

3.代码实现

二：三数之和

1.题目要求

2.解题思路 

3.代码实现

三：数组中只出现一次的两个数字 

1.题目要求

2.解题思路

3.代码实现

---

一：两数之和

1.题目要求

相信很多人刷题的第一道就是两数之和，然后就被劝退了，我们先看一下题目内容： 

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

示例：

输入：[3,2,4],6

复制返回值：[2,3]

复制说明：因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]

2.解题思路

        首先采用暴力算法很容易，两个for循环，但是这样时间复杂度很高，我们这时候可以换一种思维，题目叫求两个数之和是目标数，我们可以换成目标数与数组中某一个数之差等于数组中另一个数，采用一个HashMap实现。 

3.代码实现

import java.util.*;
 
 
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        HashMap map = new HashMap<>();
        int[] res = new int[2];
        for(int i = 0; i < numbers.length; i++) {
            if(!map.containsKey(target - numbers[i])) {
                map.put(numbers[i],i + 1);
            } else {
                int res1 = map.get(target - numbers[i]);
                res[0] = res1;
                res[1] = i + 1;
                return res;
            }
        }
        return res;
    }
}

二：三数之和

1.题目要求

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

注意：

1. 三元组（a、b、c）中的元素可以按任意顺序排列。
2. 解集中不能包含重复的三元组。

示例：

输入：[-10,0,10,20,-10,-40]

复制返回值：[[-10,-10,20],[-10,0,10]]

2.解题思路 

直接找三个数字之和为某个数，太麻烦了，我们是不是可以拆分一下：如果找到了某个数aaa，要找到与之对应的另外两个数，三数之和为0，那岂不是只要找到另外两个数之和为−a-a−a？这就方便很多了。

因为三元组内部必须是有序的，因此可以优先对原数组排序，这样每次取到一个最小的数为aaa，只需要在后续数组中找到两个之和为−a-a−a就可以了，我们可以用双指针缩小区间，因为太后面的数字太大了，就不可能为−a-a−a，可以舍弃。

3.代码实现

import java.util.*;
public class Solution {
    public ArrayList> threeSum(int[] num) {
        ArrayList> res = new ArrayList<>();
        if(num.length < 3) return res;
        Arrays.sort(num);
        for(int i = 0; i < num.length - 2; i++) {
            if(i > 0 && num[i] == num[i - 1]) continue;
            int temp = num[i];
            int left = i + 1;
            int right = num.length - 1;
            while(left < right) {
                if(num[left] + num[right] < -temp) {
                    left++;
                } else if(num[left] + num[right] > -temp) {
                    right--;
                } else {
                    ArrayList arr = new ArrayList<>(Arrays.asList(temp,num[left],num[right]));
                    res.add(arr);
                    //去重
                    while(left + 1 < right && num[left] == num[left + 1]) {
                        left++;
                    }
                    while(right - 1 > left && num[right - 1] == num[right]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

三：数组中只出现一次的两个数字 

1.题目要求

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求：空间复杂度 O(1)，时间复杂度O(n)

提示：输出时按非降序排列。

示例

输入：[1,4,1,6]

复制返回值：[4,6]

复制说明：返回的结果中较小的数排在前面

2.解题思路

我们可以先将数组进行排序，然后再依次遍历每个数，假如当前遍历这个数等于下一个数，那么说明这两个数是相同的，下标直接+2；否则说明这个数在数组中只出现一次，放入结果集，下标+1。 

3.代码实现

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        Arrays.sort(array);
        int[] res = new int[2];
        int count = 0;
        for(int i = 0;i <= array.length - 2;) {
            if(array[i] == array[i + 1]) {
                i = i + 2;
                if(i > array.length - 2) break;
            } else {
                res[count++] = array[i];
                i++;
            }
        }
        if(array[array.length - 1] != array[array.length - 2]) res[count++] = array[array.length - 1];
        return res;
    }
}

今天的题目介绍就到这，实践才是检验真理的唯一标准，算法光看还不行，必须得自己动手练习，传送门链接，一键直达练习场 ：牛客网  刷题|面试|找工作神器