LeetCode踩坑集锦

发表于 更新于 分类于 ， 阅读次数：

写在前面

寒假（假装）看完《数据结构与算法分析》之后决定是时候开始做LeetCode的题目了，在这里记录下一些LeetCode过程中遇到的坑，做LeetCode不仅是对算法的一种考验，也是对Java基础知识的一种考查，在Java基础并不是太好的现在做一定会漏洞百出，在这里统一做一个记录，也会写下对一些题目的想法。

LeetCode

Two Sum

直观上的方法是遍历所有元素对找出答案，看了解答以后发现可以用Hash表实现，Hash表可以进行对另一个元素的快速查找并返回对应的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (Integer num : map.keySet()) {
        if (map.containsKey(target - num) && !Objects.equals(map.get(num), map.get(target - num))) {
            return new int[]{map.get(num), map.get(target - num)};
        }

    }
    return null;
}

上面的代码在用例[3,3] 6的时候返回结果为null，原因是第7行中第二个判断条件不成立，由于构建hash表的时候后面一个[3,1]覆盖了前面的[3,0]导致无法同时找到两个位置。（提醒了hash表一对一的性质，后面加入的元素如果key相同会覆盖前面的元素）

解决办法是不遍历key而是直接遍历nums数组，比较循环的索引和hash表的value，这样可以保证找到对应的那个位置不同的元素位置。

Rotate Array

1
2
3
4
5
6
7
8
9
10
public static void rotate(int[] nums, int k) {
    for (int i = 0; i < k; i++) {
        int[] temp = new int[nums.length];
        temp[0] = nums[nums.length - 1];
        for (int j = 0; j < nums.length-1; j++) {
            temp[j + 1] = nums[j];
        }
        nums = temp;
    }
}

错误的原因是没有理解数组元素传递的本质是对数组对象引用的值传递，刚开始看到这题目觉得怎么可以用java做，java都是值传递无法改变原来数组。上面的做法的结果是把一个新的数组对象的引用赋给了nums的一个拷贝，但是原来的nums并没有引用到新的地址，所以原nums还是保持不变。

查了相关资料了解到数组元素的传递与对象一样（数组也可以看成new int[]产生的对象），传递的是数组的引用的拷贝，可以通过这个引用来修改原数组的数据。