例题一：1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 例行防御编程，养成习惯
    	if (nums == null || nums.length == 0)
        return new int[]{};
        Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < nums.length; i++){
                    if(map.containsKey(nums[i])){
                            return new int[] {map.get(nums[i]), i};
                    }
                    map.put(target - nums[i], i);
            }
            return new int[] {};
    }
}

例题二：447. 回旋镖的数量

多读两遍题，大概就明白了题意：就是找出所有符合三个点x,y,z，并且dis(x,y)=dis(x,z)这种点的个数。首先要明确两点间距离怎么计算，忘了是小学还是初中的知识了：

x

=

(

x

1

,

x

2

)

x=(x1,x2)

x=(x1,x2)

y

=

(

y

1

,

y

2

)

y=(y1,y2)

y=(y1,y2)

d

i

s

(

x

,

y

)

=

(

x

1

−

y

1

)

2

+

(

x

2

−

y

2

)

2

dis(x,y) = \sqrt{(x1 - y1)^{2} + (x2 - y2) ^{2}}

dis(x,y)=(x1−y1)2+(x2−y2)2

由于求的是算数平方根，所以我们算距离的时候也没必要开根号了

我们可以很容易地想到暴力解法，也就是来个三重循环

public int numberOfBoomerangs(int[][] points) {

    if (points == null || points.length <= 2)
        return 0;

    int res = 0;
    
    for (int i = 0; i < points.length; i++) {

        for (int j = 0; j < points.length; j++) {

            if (i == j)
                continue;

            for (int k = 0; k < points.length; k++) {
                
                if (k == i || k == j)
                    continue;

                if (getDistance(points[i], points[j]) == getDistance(points[i], points[k]))
                    res++;
            }
        }
    }

    return res;   
}

private int getDistance(int[] x, int[] y) {

    int x1 = y[0] - x[0];
    int y1 = y[1] - x[1];

    return x1 * x1 + y1 * y1;
}

这就相当于把题目翻译了一遍，但是提交就会发现TLE了，也不难发现时间复杂度是

O

(

N

3

)

O(N^{3})

O(N3)，也就是我们需要优化代码了。。。首先题目说n个点不同且答案考虑元组顺序，那么我们最外层循环是跑不掉了，因为需要固定每一个点。

里面两层循环可不可以优化一下呢，其实不难想，当我们固定其中一个点A的时候，并且想算距离为3的点的个数，那么我们就找出所有和点A距离为3的点，然后来一个简单的排列组合嘛！比如找到了n个距离为3的点，那么我们选择第二个点有n种方案，选择第三个点有(n - 1)个方案，那么固定点A且距离为3的所有可能就是n*(n-1)，这是说距离为3，还有许多其他距离呢，这不就又回到了我们统计元素频率的问题上了嘛，当然哈希表用起来！上代码：

public int numberOfBoomerangs(int[][] points) {

    if (points == null || points.length <= 2)
        return 0;

    int res = 0;
    Map<Integer, Integer> equalCount = new HashMap<>();

    for (int i = 0; i < points.length; ++i) {

        for (int j = 0; j < points.length; ++j) {

            int dinstance = getDistance(points[i], points[j]);
            equalCount.put(dinstance, equalCount.getOrDefault(dinstance, 0) + 1);
        }

        for (int count : equalCount.values())
            res += count * (count - 1);
        equalCount.clear();
    }

    return res;
}
    
private int getDistance(int[] x, int[] y) {

    int x1 = y[0] - x[0];
    int y1 = y[1] - x[1];

    return x1 * x1 + y1 * y1;
}

这样时间复杂度就被优化为

O

(

N

2

∗

m

a

x

(

d

i

f

f

e

r

e

n

t

d

i

s

t

a

n

c

e

c

o

u

n

t

)

)

O(N^{2} * max(different_distance_count))

O(N2∗max(differentdistancecount))

例题三：36. 有效的数独

class Solution {
    public boolean isValidSudoku(char[][] board) {
            boolean[][] rows = new boolean[9][10];
            boolean[][] cols = new boolean[9][10];
            boolean[][] boxes = new boolean[9][10];
            for(int i = 0; i < 9; i++){
                    for(int j = 0; j < 9; j++){
                            if(board[i][j] == '.')
                                    continue;
                            int boxIndex = i / 3 + j / 3 * 3;
                            int num = board[i][j] - '0';
                            if(rows[i][num] || cols[j][num] || boxes[boxIndex][num])
                                    return false;
                            rows[i][num] = cols[j][num] = boxes[boxIndex][num] = true;
                    }
            }
            return true;
    }
}

例题四：645. 错误的集合

方法一：哈希表

class Solution {
    public int[] findErrorNums(int[] nums) {
        boolean[] arr = new boolean[nums.length];
            int dup = 0, loss = 0;
            for(int each : nums){
                    if(!arr[each-1]){
                            arr[each-1] = true;
                    }else{
                            dup = each;
                    }
            }
            for(int i = 0; i < arr.length; i++){
                    if(!arr[i])
                            loss = i + 1;
            }
            return new int[]{dup, loss};
    }
}

时间复杂度和空间复杂度都为O(n)。

方法二：不占用额外内存

另外，还用一种方法可以将空间复杂度降到O(1)。将nums的每一个数看作下标，nums有两个相同的数即有两个下标对应同一个数，nums少一个数即有一个数没有下标与之对应。因此可以通过如下方法来解决：

class Solution {
    public int[] findErrorNums(int[] nums) {
            int dup = 0, loss = 0;
            for(int each : nums){
                    if(nums[Math.abs(each)-1] > 0)
                            nums[Math.abs(each)-1]*=-1;
                    else
                            dup =  Math.abs(each);
            }
            for(int i = 0; i < nums.length; i++){
                    if(nums[i] > 0){
                            loss = i + 1;
                            break;
                    }
            }
            return new int[]{dup, loss};
    }
}

时间复杂度是O(n)，空间复杂度也是O(1)，n为输入的数组长度。

方法三：只需一次遍历

一次遍历找到重复的数，同时计算元素和，然后用差值计算出缺少的元素。

public int[] findErrorNums(int[] nums) {

    // 简单防御编程
    if (nums == null || nums.length <= 1)
        return new int[]{};

    Set<Integer> set = new HashSet<>();
    int repeat = 0, lost = 0, sum = 0, len = nums.length;

    for (int i = 0; i < len; i++) {
        sum += nums[i];
        if (!set.add(nums[i]))
            repeat = nums[i];
    }
    // 自然数求和
    lost = (len * (len + 1)) / 2 - sum + repeat;

    return new int[]{repeat, lost};
}

例题五：面试题04.01. 节点间的通路

思路

首先这道题说的挺清楚的，还记得讲义里哈希表的作用之一是建立图对吧，这道题就是一道典型的先建图后搜索。

首先简单的说一下什么是有向图

大白话就是有很多个点，这些点用线来连接起来所构成的数据结构。
线如果是没有方向的就是无向图，反之，就是有向图。
我们之前讲的链表，树其实都是有向图的特殊情况。
下面回到这个问题， 题中说了图中可能存在自环和平行边，那再简单说下这两个概念：

自环：比如有一个节点A，它有一条边指向了自己。
平行边：比如有两个节点A,B，有两条或以上A→B的边。
好吧，那么我们用哈希表来表示图吧！怎么表示呢，哈希表的键来作为边的起始点，值（这里用Set作为值，为啥不用List，小伙伴们可以自行思考）用来存储以该起始点向外指出的边集。

因此构图代码如下：

Map<Integer, Set<Integer>> map = new HashMap<>();
for (int[] edge : graph) {

    Set<Integer> cur = map.getOrDefault(edge[0], new HashSet<>());
    cur.add(edge[1]);
    map.put(edge[0], cur);
}

这样构建出来的图自动忽略掉了平行边的情况，原因请自己思考（不难的）。

好啦，图构建完了，下一步就非常容易啦，因为就是一个搜索问题，找到指定的两个点之间是否存在一条路径，可以用深度优先搜索，也可以用广度优先搜索，因为大家之前有练习过树的遍历，因此我下面给出深度优先搜索的代码，由于我们有visited数组，自环这种特殊情况自动就被滤除出去了：

代码

class Solution {

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {

        Map<Integer, Set<Integer>> map = new HashMap<>();

        for(int[] edge : graph){

            Set<Integer> curr = map.getOrDefault(edge[0], new HashSet<Integer>());

            curr.add(edge[1]);

            map.put(edge[0], curr);

        }

        boolean[] visited = new boolean[n];

        return dfs(map, visited, start, target);

    }

    public boolean dfs(Map<Integer, Set<Integer>> map, boolean[] visited, int start, int target){

        if(start == target)

            return true;

        if(!map.containsKey(start))

            return false;

        visited[start] = true;

        boolean flag = false;

        for(int each : map.get(start)){

            if(!visited[each] && dfs(map, visited, each, target))

                flag =