Payne的小站

写在前面

把LeetCode上的题目分类后，系统学习算法，分类来源

q1_两数之和

思路1

直接遍历两遍，找到答案直接返回。o(n²)
代码

public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

思路2

利用hash的特性，少一次遍历。o(n)
代码

 public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }

q387_字符串中的第一个唯一字符

思路

先遍历一遍s，把string转成存放char和其对应数量的map，然后在遍历s，找到第一个数量为1的char，如果没有返回-1。o(n)
代码

  public int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        for (int i = 0; i < chars.length; i++) {
            if (map.get(chars[i]) == 1) {
                return i;
            }
        }
        return -1;
    }

上述代码，可以做如下优化

            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }

            //优化为
             map.put(c, map.getOrDefault(c, 0) + 1);